beecrowd | 2893
# Fibonac^{k}i

**Timelimit: 1**

By Fabiano S. Oliveira, UERJ Brazil

Néchi is a very smart guy. He soon realized in the early years of his academic life that it is a good idea to look for patterns contained in the description of problems to memorize them. It is curious to observe the way he memorized the Fibonacci sequence; he thought as follows: let **k** be the number of letters "c" contained in "Fibonacci". Start the sequence by 0,1, ..., **k**-1 and obtain the next element of the sequence by the sum of the immediately preceding k elements. Develop a program to compute an arbitrary element of the Fibonac** ^{k}**i sequence, as Néchi likes to call the problem.

The first line of the input is composed of the integer 1 ≤ **T** ≤ 10 which constitutes the number of test cases. The following **T** lines consist of the test cases, one per line. A test case consists of an integer 2 ≤ **k** ≤ 10^{5} followed by an integer 1 ≤ **N** ≤ 2×10^{5}.

One line per test case should be written with the remainder of the division of the **N**-th element of the Fibonac** ^{k}**i sequence by

Input Sample | Output Sample |

5 |
3 |