定义：f0=f1=1, fn=fn-1+fn-2(n>=2)。{fi}称为Fibonacci数列。 输入n，求fn mod q。其中1<=q<=30000。 Input format： 第一行一个数T(1<=T<=10000)。 以下T行，每行两个数，n，q(n<=109, 1<=q<=30000)、 Output format： 文件包含T行，每行对应一个答案。