1960 年，IBM 的 Donald Wall 在怀特普莱恩斯证明了斐波那契（Fibonacci）数列的每一项对模 $m$ 取余后形成的序列是周期性的。
例如，斐波那契数列的前十项及其对 $11$ 取余后的余数如下：
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $F(n)$ | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
| $F(n) \pmod{11}$ | 1 | 1 | 2 | 3 | 5 | 8 | 2 | 10 | 1 | 0 |
由余数构成的序列随后会重复。令 $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