斐波纳契的秘密

某某学者发现，将斐波那契数列mod $M$会呈现周期性。比如下面以$M = 11$为例：

n | 1 2 3 4 5 6 7 8 9 10
F(n) | 1 1 2 3 5 8 13 21 33 55
F(n) mod 11 | 1 1 2 3 5 8 2 10 1 0

我们可以知道当$n = 11$时和$n = 1$时相等且以后会周期性重复之前的数字，即当$M = 11$时，周期长度为$10$.我们假设$F(M)$为周期的长度，则$F(11) = 10$。另外我们发下一些有趣的性质：
如果$M > 2，F（M）$为偶数。
$F(M) \leq M^2 - 1$
$F(2n) = 3 * 2^{n - 1}$
$F(5n) = 4 * 5n$
$F(2 * 5n) = 6n$
$F(10n) = 15 * 10^{n - 1} (n > 2)$
现在我们想知道给定$M$，求$F（M）$是多少？

第一行 $T$，表示 $T$个测试样例，$(1 \leq T \leq 1000)$，接下来$T$行，每行两个整数 $N, M$
$N$表示第几个样例，$M(2 \leq M \leq 1000000)$如题目描述。

输出当前样例编号（第几个样例）和求得的$F(M)$.

4
1 4
2 5
3 11
4 123456

1 6
2 20
3 10
4 15456

2015中科院首届“斯伦贝谢”杯Debug大赛