問題文

次のような問題を考えます：

入力に $2$ 個の整数 $N, M$ が与えられます。

$\displaystyle Nk+M \equiv 0 \pmod{10^9} $

を満たす正整数 $k$ が存在するか否かを判定し、存在する場合はそのような $k$ の最小値を求めてください。

ただし整数 $n$ に対し $n \equiv 0 \pmod{10^9}$ とは $n$ が $10^9$ で割り切れるということを表します。

入力の最初に正整数 $T$ が与えられます。その後 $T$ 個の問題に答えてください。

入力

$T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力 $N,M$ を $N_t, M_t$ と置きます。

この時、入力は以下の形式で標準入力から $1 + T$ 行で与えられます：

• $1$ 行目に $T$ が与えられます。
• $T$ 以下の各正整数 $t$ に対し、$1 + t$ 行目に $t$ 個目の問題に対する問題の入力 $N_t, M_t$ が半角空白区切りで与えられます。

$T$
$N_1$ $M_1$
$\vdots$
$N_T$ $M_T$

制約

入力は以下の制約を満たします：

• $T$ は $1 \leq T \leq 10^5$ を満たす整数
• $T$ 以下の任意の正整数 $t$ に対し、
• $N_t$ は $1 \leq N_t \leq 10^{18}$ を満たす整数
• $M_t$ は $1 \leq M_t \leq 10^{18}$ を満たす整数

出力

$T$ 以下の各正整数 $t$ に対し、

$\displaystyle N_t k+M_t \equiv 0 \pmod{10^9} $

を満たす正整数 $k$ が存在する場合はその最小値を $t$ 行目に出力し、存在しない場合は-1と $t$ 行目に出力してください。

最後に改行してください。

サンプル

4
1 1
1 2
2 1
3 1

999999999
999999998
-1
333333333