Note : Do not use cin/cout for this problem, it might give TLE. use scanf/printf instead.

The task of this problem is very simple.
You will be given two integers N and K.
You have the find out the Nth fibonacci number and then print its Kth digit from the end.

consider following initial conditions :

Fib[1]=1
Fib[2]=1

Input :

First line will contain an integer T(number of testcase).
Each of the next T lines contains two integers N and K.

Output :

For each testcase output the required answer on a new line.

Constraints :

1<=T<=10^6
1<=N<=10^6
1<=K<=15