Project Euler #115: Counting block combinations II

_{This problem is a programming version of Problem 115 from projecteuler.net}

A row measuring units in length has red blocks with a minimum length of units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.

Let the fill-count function, , represent the number of ways that a row can be filled.

For example, and .

That is, for , it can be seen that is the smallest value for which the fill-count function first exceeds one million.

In the same way, for , it can be verified that and , so is the least value for which the fill-count function first exceeds one million.

For given , find the least value of for which .

Input Format

First line contains an integer denoting the number of test cases.
Each of the following lines contain two integers and .

Constraints

Output Format

For each of test cases print one line containing a single integer - the answer to a problem.

Sample Input

2
3 1000000
10 1000000

Sample Output

30
57