HZNUOJ

KK与蛇之最后一战

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:392     AC:88     Score:94.91

Description

众所周知KK很怕蛇,为了战胜自己的心魔,KK选择与蛇后卡西奥佩娅最后一战,但是卡西奥佩娅很狡猾,她把自己藏在很多的房间当中,而KK运气很好,一下子就在一排房间中找到了卡西奥佩娅所处的房间,但是每个房间都是有一个独特的防护罩的,防护罩只有特定的密码才能够破解。

KK通过观察,发现这些房子的密码和斐波那契数列有关,斐波那契数列是{1,1,2,3,5,……}也就是第一项和第二项是1,从第三项开始,每一项都是前两项之和,而这些房子的标号也是从1开始,每一间房子都是对应的斐波那契数列取模p的余数。

KK现在知道了p是多少,也知道卡西奥佩娅在第n个房间。但是KK只有一次使用自己的神力的机会,如果他把力量用在了打破防御罩上,KK就打不过卡西奥佩娅,而且又会被他的队友嘲笑了,为了KK能够打败卡西奥佩娅,你能帮KK破解房子的密码吗?

Input

第一行是一个T,代表有T组测试样例。(T<=10)

对于每组测试样例,只有一行输入,包括了p和n两个数字。

p代表密码的取模数,n代表卡西奥佩娅所在的房间。(1<p<=1000,1<n<=1e12).

Output

输出卡西奥佩娅所在房间的密码(行末没有多余空格)。

Samples

input
3 2 3 2 4 2 5
output
0 1 1
input
1 5 100002
output
1

Author

YU, Saikang

Source

2018年秋季学期程序设计基础(C语言)第一次考试