1960 年，IBM 的 Donald Wall 在怀特普莱恩斯证明了斐波那契（Fibonacci）数列的每一项对模 $m$ 取余后形成的序列是周期性的。

例如，斐波那契数列的前十项及其对 $11$ 取余后的余数如下：

由余数构成的序列随后会重复。令 $k(m)$ 为重复子序列的长度；在本例中，我们看到 $k(11) = 10$。

Wall 还证明了其他一些性质，你可能会觉得很有趣：

• 如果 $m > 2$，则 $k(m)$ 是偶数。
• 对于任何偶数 $n > 2$，都存在 $m$ 使得 $k(m) = n$。
• $k(m) \le m^2 - 1$
• $k(2^n) = 3 \times 2^{(n-1)}$
• $k(5^n) = 4 \times 5^n$
• $k(2 \times 5^n) = 6n$
• 如果 $n > 2$，则 $k(10^n) = 15 \times 10^{(n-1)}$

对于本题，你需要编写一个程序，计算不同模数 $m$ 下重复子序列的长度 $k(m)$。

输入格式

输入的第一行包含一个整数 $P$ ($1 \le P \le 1000$)，表示随后数据集的数量。每个数据集占一行，由两个以空格分隔的整数 $N$ 和 $M$ 组成。$N$ 是数据集编号，$M$ 是模数 ($2 \le M \le 1,000,000$)。

输出格式

对于每个数据集，输出一行。内容为数据集编号 ($N$)，后跟一个空格，再跟 $M$ 的重复子序列长度 $k(M)$。

样例

输入格式 1

5
1 4
2 5
3 11
4 123456
5 987654

输出格式 1

1 6
2 20
3 10
4 15456
5 332808