Fibonacci sequence is well-known in the world. We define Fibonacci sequence as follows: F(0) = 0, F(1) = 1. F(n) = F(n-1) + F(n-2), n>=2. It’s easy for us to calculate F(n) mod m. But this time we want to make the problem more difficult. We want to calculate the formula:
is the combination number.
First line is the testcase T. Following T lines, each line is two integers n, m ( 0 ≤ n ≤ 10^9, 1 ≤ m ≤ 30000 )
Output the answer mod m.