Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
正整数 A,\ B が与えられます。
非負整数 X,\ Y であって、 B+Y が A+X の倍数となるようなものに対する X+Y の最小値を求めてください。
T 個のテストケースが与えられるので、それぞれについて求めてください。
制約
- 1 \leq T \leq 100
- 1 \leq A,\ B \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
T \mathrm{case}_{1} \mathrm{case}_{2} \vdots \mathrm{case}_{T}
各ケースは以下の形式で与えられます。
A B
出力
T 行出力してください。 i 行目には i 番目のテストケースに対する答えを出力してください。
入力例 1
5 11 23 8 16 4394 993298361 95392025 569922442 8399283 10293
出力例 1
2 0 65 2429708 8388990
1 個目のテストケースについて、X=1,\ Y=1 とすると B+Y=24 は A+X=12 の倍数になります。このとき X+Y=2 であり、X+Y はこれより小さくすることはできないので答えは 2 です。
2 個目のテストケースについて、X=0,\ Y=0 とすると B+Y=16 は A+X=8 の倍数になります。
Score : 500 points
Problem Statement
You are given positive integers A and B.
Find the minimum value of X+Y for non-negative integers X and Y such that B+Y is a multiple of A+X.
You have T test cases to solve.
Constraints
- 1 \leq T \leq 100
- 1 \leq A,\ B \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
T \mathrm{case}_{1} \mathrm{case}_{2} \vdots \mathrm{case}_{T}
Each case is in the following format:
A B
Output
Print T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
5 11 23 8 16 4394 993298361 95392025 569922442 8399283 10293
Sample Output 1
2 0 65 2429708 8388990
For the first test case, if we let X=1 and Y=1, then B+Y=24 will be a multiple of A+X=12. Here, we have X+Y=2, and there is no way to make X+Y smaller, so the answer is 2.
For the second test case, if we let X=0 and Y=0, then B+Y=16 will be a multiple of A+X=8.