問題文

0,1,2,3,4,5,6,7,8,9 からなる文字列 $X$と正整数 $M$ が与えられます。 ここで、制約により $X$ の $1$ 文字目は0でないことが保証されています。

以下の条件をすべて満たす文字列 $Y$ が存在するか判定し、存在する場合は $1$ つ出力してください。

• $Y$ は 0,1,2,3,4,5,6,7,8,9 からなる。
• $|X| \leq |Y| \leq 18$
• $X$ は $Y$ の接頭辞かつ接尾辞である。
• $Y$ を $10$ 進数の数値と解釈した値は、 $M$ の倍数である。

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

制約

• $T$ は整数
• $M$ は全て整数
• $X$ は 0,1,2,3,4,5,6,7,8,9 からなる
• $1 \leq T \leq 10^5$
• $1 \leq M \leq 10^9$
• $1\leq|X|\leq3 $
• $X$ の $1$ 文字目は 0 でない

入力

$T$
$\mathrm{case_1}$
$\mathrm{case_2}$
$\vdots$
$\mathrm{case}_T$

ここで、 $\mathrm{case}_i$ は $i$ 番目のテストケースを表す。各テストケースは以下の形式で与えられる。

$X   M$

出力

$T$ 行出力してください。

$i$ 行目では、 $i$ 番目のテストケースについて、条件をすべて満たす $Y$ が存在しない場合は -1 を出力してください。存在する場合は $1$ つ出力してください。

条件を満たす解が複数存在する場合、どれを出力しても正解とみなされます。

サンプル

5
6 3
1 4
111 271
999 989001099
12 800

606
-1
11111
999000000000000999
-1