A more fun version of a simpler question... :)
Each input file consists of T test cases, where each test case follows the following format:
You are given two natural numbers N and M. Write a program that outputs the remainder of the Nth Fibonacci number when divided by M.
For those who were sleeping during lesson, the Fibonacci sequence is generated as follows:
f0 = 0
f1 = 1
fi = fi-1 + fi-2 for i ≥ 2
You are supposed to output an integer fN (mod M).
The first line of the input contains one integer T (1 ≤ T ≤ 100000)
The next T lines of the output contain two integers each, N and M (1 ≤ N, M ≤ 1,000,000,000).
For each of the T test cases, output the integer fN (mod M).
1 3 1337
3 3 1337 10 1337 10 54
2 55 1