Problem D
Curupira

Curupiras are magical beings that inhabit the forest. They love nature and spend most of their time protecting it and pranking hunters and explorers amid the trees.

Sometimes they enjoy the company of humans and learn a thing or two from them. For instance, they love the idea of every now and then celebrating their birthday.

Since they haven’t agreed upon the number of days in a curupira year, each one has picked a number to be able to celebrate its birthday. The $i$-th curupira picked $n_ i$, which means it will commemorate its birthday every $n_ i$ days.

All curupiras were born equal on the day they call day $0$. They identify each following day by the number of elapsed days between it and day $0$.

Each curupira $i$ also has a lucky digit $k_ i$. It considers a number lucky if it only contains digits $k_ i$, other than possibly some trailing zeroes.

Curupiras are very superstitious and will only throw parties at days that are lucky numbers. Of course it makes no sense to throw a party in a day which it isn’t their birthday.

So for each curupira $i$ help it find out what is the first day $m_ i$ in which it can throw a party. In other words, find the smallest $m_ i$ which is a multiple of $n_ i$ formed by a sequence of digits $k_ i$ optionally followed by a sequence of digits $0$.

Input

The first line of input contains $q$ ($1 \le q \le 100\, 000$), the number of curupiras.

The following $q$ lines describes the numbers for each curupira. The $i$-th line contains the number $n_ i$, $1 \le n \le 10^5$ and a digit $k_ i$, $1 \le k \le 9$, as described above.

Output

For each of the $q$ curupiras you must find $m_ i$ as described in the statement. Since $m_ i$ can be huge, print only $a_ i$ and $b_ i$, where $a_ i > 0$ is the number of digits $k_ i$ in $m_ i$ and $b_ i \ge 0$ is the number of trailing digits $0$ in $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