Daisy 最近刚学习了整数的整除性规则，并对此产生了浓厚的兴趣。她学到的其中一个测试是关于 3 的整除性测试：你可以求出一个十进制数所有数字的和，并检查该和是否能被 3 整除。此外，所得的数字和与原数模 3 同余——即模 3 的余数保持不变。例如，$75 \equiv 7 + 5 \pmod 3$。Daisy 特别关注这类保持余数的整除性测试。

她还学习了更多关于十进制整数（基数为 10）的例子：

• 对于模 11 的整除性测试，求数字的交错和。从最后一位（最低位）开始计数，将奇数位置上的数字（最后一位、倒数第三位等）相加，并减去偶数位置上的数字（倒数第二位、倒数第四位等），得到的和与原数模 11 同余。例如，$123 \equiv 1 - 2 + 3 \pmod{11}$。
• 对于模 4 的整除性测试，保留最后两位数字。它们的值与原数模 4 同余。例如，$876543 \equiv 43 \pmod 4$。
• 对于模 7 的整除性测试，求三位一组的数字的交错和。例如，$4389328 \equiv 4 - 389 + 328 \pmod 7$。

在其他进制中也能找到类似的测试。例如，对于八进制数（基数为 8），要测试模 5 的整除性，可以求两位一组的数字的交错和。例如，$1234_8 \equiv -12_8 + 34_8 \pmod 5$。

Daisy 想要为给定的基数 $b$ 寻找这类规则。她对以下三种整除性规则感兴趣：

• 类型 1 —— 取基数为 $b$ 的整数的最后 $k$ 位。
• 类型 2 —— 取基数为 $b$ 的整数的 $k$ 位一组的数字之和。
• 类型 3 —— 取基数为 $b$ 的整数的 $k$ 位一组的数字的交错和。

并非总能找到这样的整除性规则。例如，在基数为 10 时，不存在模 6 的此类测试，尽管存在其他测试 6 的整除性的方法。

给定基数 $b$ 和模数 $n$，Daisy 想知道存在此类整除性测试的最小分组大小 $k$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$ —— 测试数据的组数。接下来的 $t$ 行描述了这些测试。

每个测试包含一行，包含两个整数 $b$ 和 $n$ —— 基数和模数（$b, n \ge 2$）。输入中所有 $b$ 的总和不超过 $10^6$，所有 $n$ 的总和不超过 $10^6$。

输出格式

输出 $t$ 行 —— 每行对应一个测试的结果。如果对于给定的 $b$ 和 $n$ 不存在整除性测试，则输出一个整数 0。否则，输出两个整数 $a$ 和 $k$，其中 $a$ 是整除性测试的类型（1、2 或 3），$k$ 是该测试中一组的位数，且 $k$ 是所有可能的整除性测试中最小的。

样例

输入 1

6
10 3
10 11
10 4
10 7
8 5
10 6

输出 1

2 1
3 1
1 2
3 3
3 2
0