#3091. Kingdom Test

Kingdom Test

Background

SABRINA\mathbb{S}\mathbb{A}\mathbb{B}\mathbb{R}\mathbb{I}\mathbb{N}\mathbb{A} 要接受大祭司 LINUXSS\mathbb{L}\mathbb{I}\mathbb{N}\mathbb{U}\mathbb{X}\mathbb{S}\mathbb{S} 的考验。

Description

已知有一个非负整数 NN 可以表示为 10k=N×P+Q10^{k} = N \times P + Q ,其中 P,QP,Q 是已知参数,且 0Q<P200000 \leq Q < P \leq 20000

SABRINA\mathbb{S}\mathbb{A}\mathbb{B}\mathbb{R}\mathbb{I}\mathbb{N}\mathbb{A} 要在 1.00s1.00s 内说出上式成立且 kk 能取得的最小值,否则它将会被赶出 DeduccioˊnFiscal\tt Deducción\,\,Fiscal 王国!

Format

Input

第一行输入一个整数 TT 表示数据组数。

接下来 TT,每行两个数 P,QP,Q,如题所示。

Output

对于每一组数据,输出一个整数表示答案,无解输出 1-1,否则输出 kk

样例 #1

样例输入 #1

3
15 10
1937 1213
18899 18779

样例输出 #1

1
5
18