#P1535. Fibonacci数列(五)

Fibonacci数列(五)

上传这道题目的时候,rihkddd有些为难了,因为仅仅NYOJ上关于Fibonacci的题目就有至少3题了,这又是个关于Fibonacci的题目,应该给它起个什么名字呢?干脆就叫“还是Fibonacci”吧!
题目的意思很简单:F(n)就是传说做那个叫做还是Fibonacci的数列了:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)   (n>2)……,然后对于每个给定的n求出下面这个式子的值mod给定的m的值。
(貌似很可怕的数学式子……)

Input

第一行一个数n,表示测试数据组数。
接下来有n行数,每行数有两个数,分别是n(n<10^9),m(m<10^5)。

Output

输出结果,每组输出占一行。

Sample Input

2
1 30000
2 30000

Sample Output

1
3

HINT

</p>

Source