记录编号	476520	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	胡嘉兴	是否通过	通过
代码语言	C++	运行时间	2.738 s
提交时间	2017-11-25 11:59:23	内存使用	0.31 MiB

#include<bits/stdc++.h>
#define N 5
#define ll long long
using namespace std;
ll p;
struct martrix
{
    ll A[N][N];
    void init()
    {
        memset(A, 0, sizeof(A));
        A[1][2] = A[2][1] = A[2][2] = 1;
    }
    martrix operator * (martrix& a)const{
        martrix ans;
        memset(ans.A, 0, sizeof(ans.A));
        for(int i = 1; i < 3; i++)
        {
            int j = 1;
            for(int k = 1; k < 3; k++)
            {
                ans.A[i][j] += A[i][k]*a.A[k][j];
            }
            ans.A[i][j] %= p;
        }
        /*for(int i = 1; i <= 1; i++)
        {
            for(int j = 1; j <= 3; j++)
            {
                for(int k = 1; k <= 3; k++)
                {
                    ans.A[i][j] += A[i][k]*a.A[k][j];
                    ans.A[i][j] %= MOD;
                }
            }
        }*/
        return ans;
    }
    martrix ppow()const{
        martrix ans;
        memset(ans.A, 0, sizeof(ans.A));
        for(int i = 1; i < 3; i++)
        {
            for(int j = 1; j < 3; j++)
            {
                for(int k = 1; k < 3; k++)
                {
                    ans.A[i][j] += A[i][k]*A[k][j];
                }
                ans.A[i][j] %= p;
            }
        }
        return ans;
    }
};
martrix t, ans;
void qpow(int k)
{
    t.init();
    memset(ans.A, 0, sizeof(ans.A));
    ans.A[2][1] = 1;
    while(k)
    {
        if(k&1)
        {
            ans = t*ans;
        }
        t = t.ppow();
        k >>= 1;
    }
    printf("%lld\n", ans.A[2][1]%p);
}
int main()
{
    int T, n;
    freopen("eins.in", "r", stdin);
    freopen("eins.out", "w", stdout);
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%lld", &n, &p);
        if(n==0)
        {
            puts("0");
            continue;
        }
        qpow(n-1);
    }
}