The Fibonacci Numbers {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...} are defined by the recurrence: F(0)=0 F(1)=1 F(n)=F(n-1)+F(n-2) We defined S(n)=1+2+3+...+F(n). Write a program to calculate S(n). The result may be large,just output S(n)%m instead.

The first line of the input file contains a single integer T<=100, the number of test cases. The following T lines,each contains two integer n ( 1 <= n <= 1000,000,000 )and m (0 < m <= 100,000,000), and you are expected to calculate S(n)%m.

Output S(n)%m on a separate line.

chenwenwen