SP13420 FMODF - Fimodacci

After solving [Fib-Factorization](http://www.spoj.com/problems/BMS1988/) and [ModFib-Period](http://www.spoj.com/problems/PISANO/), you would probably be interested by solving this new task: Simply compute Fib(N) mod Fib(K), where Fib(N) denotes the Nth term of the Fibonacci sequence. (If N

The input begins with the number T of test cases in a single line. In each of the next T lines there are two integers N, K.

For each test case, on a single line, print Fib(N) mod Fib(K).