FMODF  Fimodacci
After solving FibFactorization and ModFibPeriod, 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<2 Fib(N)=N, else Fib(N)=Fib(N1)+F(N2)).
Input
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.
Output
For each test case, on a single line, print Fib(N) mod Fib(K).
Example
Input: 2 5 5 13 5 Output: 0 3
Constraints
1 < T < 10^5 1 < N < 10^18 1 < K <= 10^3
Edit(20170211) : New time limit (after compiler changes).
hide comments
[Lakshman]:
20130730 10:59:26
@Franky I don't understand test cases Fib(K)5=20 and fib(5)=5, why answer is 0,also fib(13)=233%20 =13 why answer is 3, Might be I m thinking wrong.


[Rampage] Blue.Mary:
20130309 13:31:16
Your Python 3 code run under 0.7 sec > Time limit should be at least 2 sec. My Pike code output 80000 answers in ~1sec. I don't think that code should get TLE.


Fernando Fonseca [ITA]:
20130309 13:31:16
For anyone using Python, you might want to read using sys.stdin.readlines(). I don't know what other tricks Francky used, but that got my code to barely pass the time limit.


preetam:
20130309 13:31:16
guess a java solution is not even expected :P


符号器:
20130309 13:31:16
@Robert:what is your time complexity....i m doing in T*(log(n)+log(k)) but still tle....


Francky:
20130309 13:31:16
@Robert : K=2 is included, sorry about that.

Added by:  Francky 
Date:  20130120 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 