- All Contests
- ProjectEuler+
- Project Euler #140: Modified Fibonacci golden nuggets

# Project Euler #140: Modified Fibonacci golden nuggets

# Project Euler #140: Modified Fibonacci golden nuggets

_{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
```