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.