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 .
First line contains an integer denoting the number of test cases.
Each of the following lines contain two integers and .
For each of test cases print one line containing a single integer - the answer to a problem.