#P9460. X+Y 的最小值

    ID: 6001 传统题 1000ms 256MiB 尝试: 6 已通过: 3 难度: 5 上传者: 标签>CF1800普及+/提高-固定一个变量消去另一维向下取整与向上取整整除分块

X+Y 的最小值

题面翻译

给定两个正整数 A,BA,B,求满足 B+YB+Y 为 A+XA+X 倍数的非负整数 X,YX,Y 中,X+YX+Y 的最小值。

多组数据。

数据范围:1≤T≤1001\leq T\leq100,1≤A,B≤1091\leq A,B\leq10^9,其中 TT 为数据组数。

题目描述

正整数 A, B A,\ B が与えられます。

非負整数 X, Y X,\ Y であって、 B+Y B+Y が A+X A+X の倍数となるようなものに対する X+Y X+Y の最小値を求めてください。

T T 個のテストケースが与えられるので、それぞれについて求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

T T case1 \mathrm{case}_{1} case2 \mathrm{case}_{2} ⋮ \vdots caseT \mathrm{case}_{T}

各ケースは以下の形式で与えられます。

A A B B

输出格式

T T 行出力してください。 i i 行目には i i 番目のテストケースに対する答えを出力してください。

样例 #1

样例输入 #1

5
11 23
8 16
4394 993298361
95392025 569922442
8399283 10293

样例输出 #1

2
0
65
2429708
8388990

提示

制約

  • 1 ≤ T ≤ 100 1\ \leq\ T\ \leq\ 100
  • 1 ≤ A, B ≤ 109 1\ \leq\ A,\ B\ \leq\ 10^9
  • 入力される値はすべて整数

Sample Explanation 1

1 1 個目のテストケースについて、X=1, Y=1 X=1,\ Y=1 とすると B+Y=24 B+Y=24 は A+X=12 A+X=12 の倍数になります。このとき X+Y=2 X+Y=2 であり、X+Y X+Y はこれより小さくすることはできないので答えは 2 2 です。 2 2 個目のテストケースについて、X=0, Y=0 X=0,\ Y=0 とすると B+Y=16 B+Y=16 は A+X=8 A+X=8 の倍数になります。