喵喵的遗憾

Time Limit: 20000/10000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

喵喵因为太弱,没有进Final,终身遗憾。她就挂在了这个题目上。

已知:

F0 = 1 , F1 = 1 , F2 = 2 , Fn = Fn-1+Fn-2

求:

FFFn Mod P

( 也就是 F[ F[ F[n] ] ]  % P ) 

 

Input

第一行一个整数 T 代表数据组数(T ≤ 20000)。                                                <del> 喵以人格担保时限肯定够!!!</del>

以下每行两个整数 N , P (0 ≤ N ≤ 109 , 1 ≤ P ≤ 109)

Output

对于每组数据输出一个整数代表答案。

Sample Input

4
1 2
2 3
4 35
4 31 

Sample Output

1
2
34
3

Hint

F1 = 1 , F1 = 1 , F1 = 1

F2 = 2 , F2 = 2 , F2 = 2

F4 = 5 , F5 = 8 , F8 = 34

Source

Dshawn

Manager

Information
Solved Number83
Submit Number542
Problem Tags
math
number theory
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel