This problem is a programming version of Problem 140 from projecteuler.net
Consider the infinite polynomial series , where is the term of the second-order recurrence relation , and ; that is, .
For this problem we shall be interested in values of for which is a positive integer.
The corresponding values of for the first five natural numbers are shown below.
We shall call a golden nugget if is rational, because they become increasingly rarer. for example, the golden nugget is .
Let's denote the golden nugget as ; for example, .
Given and , find , i.e., . Since this sum can be very large, output it modulo .
Input Format
The first line of input contains , the number of test cases.
Each test case consists of a single line containing two space-separated integers, and .
Constraints
In the first test case:
In the second test case:
In the third test case:
Output Format
For each test case, output a single line containing a single integer, the answer for that test case.
Sample Input
2
1 2
20 20
Sample Output
7
211345365