Problem D
Curupira

Curupiras são seres mágicos que vivem na floresta. Eles amam a natureza e passam a maior parte do tempo a protegendo, pregando peças em caçadores e viajantes no meio da mata.

Às vezes eles gostam da companhia de humanos e aprendem uma coisa ou outra deles. Por exemplo, eles amam a idea de comemorar o seu aniversário de vez em quando.

Como eles não conseguiram decidir quantos dias deve haver em um ano curupira, cada um escolheu um número para celebrar seu aniversário. O $i$-ésimo curupira escolheu o número $n_ i$, o que significa que ele irá comemorar seu aniversário a cada $n_ i$ dias.

Os curupiras foram todos criados iguais, no dia conhecido como dia $0$. Eles identificam cada dia pelo número de dias passados desde o dia $0$.

Cada curupira $i$ também tem um dígito da sorte $k_ i$. Ele considera um número como da sorte se ele só contém dígitos $k_ i$, além de possivelmente alguns zeros a direita.

Curupiras são bastante supersticiosos então só darão festas em dias que são números da sorte. Claro que não faz sentido nenhum dar uma festa em um dia que não seja seu aniversário.

Então para cada curupira $i$, ajude-o a encontrar o primeiro dia $m_ i$ no qual ele pode dar uma festa. Ou seja, encontre o menor $m_ i$ que seja múltiplo de $n_ i$ e formado por uma sequência de dígitos $k_ i$ opcionalmente seguidos por uma sequência de dígitos $0$.

Input

A primeira linha de entrada contém $q$ ($1 \le q \le 100\, 000$), o número de curupiras.

As seguintes $q$ linhas dão as informações de cada um dos curupiras. A $i$-ésima linha contém o número $n_ i$, $1 \le n \le 10^5$ e o dígito $k_ i$, $1 \le k \le 9$, como descritos acima.

Output

Para cada um dos $q$ curupiras você deve encontrar $m_ i$, como descrito no enunciado. Como $m_ i$ pode ser grande, imprima somente $a_ i$ e $b_ i$, onde $a_ i > 0$ é o número de dígitos $k_ i$ em $m_ i$ e $b_ i \ge 0$ é o número de dígitos $0$ ao final de $m_ i$.

3
1 2
1 5
1 8

1 0
1 0
1 0

3
3 3
30 3
300 3

1 0
1 1
1 2

3
1 5
42 4
83162 3

1 0
6 0
966 1