众所周知KK很怕蛇，为了战胜自己的心魔，KK选择与蛇后卡西奥佩娅最后一战，但是卡西奥佩娅很狡猾，她把自己藏在很多的房间当中，而KK运气很好，一下子就在一排房间中找到了卡西奥佩娅所处的房间，但是每个房间都是有一个独特的防护罩的，防护罩只有特定的密码才能够破解。
KK通过观察，发现这些房子的密码和斐波那契数列有关，斐波那契数列是{1,1,2,3,5，……}也就是第一项和第二项是1，从第三项开始，每一项都是前两项之和，而这些房子的标号也是从1开始，每一间房子都是对应的斐波那契数列取模p的余数。
KK现在知道了p是多少，也知道卡西奥佩娅在第n个房间。但是KK只有一次使用自己的神力的机会，如果他把力量用在了打破防御罩上，KK就打不过卡西奥佩娅，而且又会被他的队友嘲笑了，为了KK能够打败卡西奥佩娅，你能帮KK破解房子的密码吗？
第一行是一个T，代表有T组测试样例。（T<=10）
对于每组测试样例，只有一行输入，包括了p和n两个数字。
p代表密码的取模数，n代表卡西奥佩娅所在的房间。（1<p<=1000,1<n<=1e12）.
输出卡西奥佩娅所在房间的密码（行末没有多余空格）。