Divisibility Test
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Daisy has recently learned divisibility rules for integers and she is fascinated by them. One of the tests she learned is a divisibility test by 3. You can find a sum of all digits of a decimal number and check if the resulting sum is divisible by 3. Moreover, the resulting sum of digits is congruent modulo 3 to the original number — the remainder modulo 3 is preserved. For example, $$$75 \equiv 7 + 5 \pmod 3$$$. Daisy is specifically interested in such remainder preserving divisibility tests.

There are more examples like that that she learned for decimal integers (integers base 10):

Similar tests can be found in other bases. For example, to test divisibility modulo 5 for octal numbers (base 8), find an alternating sum of groups of two digits. For example, $$$1234_8 \equiv -12_8 + 34_8 \pmod 5$$$.

Daisy wants to find such rules for a given base $$$b$$$. She is interested in three kinds of divisibility rules:

It is not always possible to find such a divisibility rule. For example, in base 10 there is no such test for divisibility modulo 6, even though different approaches to testing divisibility by 6 exist.

Given base $$$b$$$ and modulo $$$n$$$, Daisy wants to know the smallest group size $$$k$$$ for which such a divisibility test exits.

Input

There are several tests in the input. The first line of the input contains an integer $$$t$$$ — the number of tests. The next $$$t$$$ lines describe the tests.

Each test consists of a line with two integers $$$b$$$ and $$$n$$$ — the base and the modulo ($$$b, n \ge 2$$$). The sum of all $$$b$$$ values in the input does not exceed $$$10^6$$$, and the sum of all $$$n$$$ values in the input does not exceed $$$10^6$$$.

Output

Write $$$t$$$ lines — a line for each test in the input. On a line for a test write a single integer $$$0$$$ if the divisibility test for a given $$$b$$$ and $$$n$$$ does not exist. Otherwise, write two integers $$$a$$$ and $$$k$$$, where $$$a$$$ is the kind of the divisibility test (1, 2, or 3) and $$$k$$$ is the number of digits in a group for the test, such that $$$k$$$ is the lowest among all possible divisiblity tests for the given $$$b$$$ and $$$n$$$.

Example

Input
6
10 3
10 11
10 4
10 7
8 5
10 6
Output
2 1
3 1
1 2
3 3
3 2
0