### A Problem With Fibonacci Sequence

Time Limit: 1000 ms Memory Limit: 65536 KiB

#### Problem Description

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.

#### Input

First line is the testcase T. Following T lines, each line is two integers n, m ( 0 ≤ n ≤ 109, 1 ≤ m ≤ 30000 )

#### Sample Input

2
1 30000
2 30000

#### Sample Output

1
3

2009湖南大学校赛