/*
需要特别注意负数的取模。
最好都是__int64的运算 
if( u > mol || u < - mol)   
    u %= mol;
c[i][j] += u;
if( c[i][j] > mol )
    c[i][j] -= mol;
else if( c[i][j] < 0 )
    c[i][j] += mol;

*/ 

#include<iostream>
using namespace std;

__int64 t[4][4] = {{0,0,1,0},{0,-1,0,0},{1,0,0,0},{0,0,1,1}};

char ch ;
__int64 A, n, mol;
__int64 ans[4][4], tmp[4][4], base[4][4], c[4][4];
__int64 u;

void out( __int64 a[4][4] )
{
    int i, j;
    for ( i = 0 ; i < 4 ; i ++ ){
        for ( j = 0 ; j < 4 ; j ++ )
            cout<<a[i][j]<<' ';
        cout<<endl;
    }
}

void mult(__int64 a[4][4],__int64 b[4][4])
{
    int i, j, k;
    for ( i = 0; i < 4 ; i ++ ){
        for ( j = 0 ; j < 3 ; j ++ ){//有一列不先计算
            u = 0 ;
            for ( k = 0 ; k < 4 ; k ++ ){
                if( a[i][k] && b[k][j] )
                {
                    u += a[i][k] * b[k][j];
                    if( u > mol || u < - mol)   
                        u %= mol;
                    if( c[i][j] < 0 )
                        u += mol;
                }
            }
            c[i][j] = u;
        }
        c[i][j] = 0;
    }
    c[3][3] = 1;
    for ( i = 0 ;i < 4 ; i ++ )
        for ( j = 0 ; j < 4 ; j ++ )
            a[i][j] = c[i][j];
}

void in( __int64 & n)
{
    n = 0;
    while( ch > '9' || ch < '0')
        ch = getchar();
    while( ch >= '0' && ch <= '9' ){
        n = n * 10 +( ch - '0');
        ch = getchar();
    }
}

void build()
{
    int i, j;
    in( A ); in( n ); in( mol );
    t[0][0] = t[3][0] = A * 4 % mol * A % mol;
    t[0][1] = t[3][1] = (- A * 4 ) % mol;
    if( t[0][1] < 0 )
        t[0][1] = t[3][1] = t[0][1] + mol;
    t[1][0] = 2ll * A % mol;
    for( i = 0 ; i < 4 ; i ++ )
        for ( j = 0 ; j < 4 ; j ++ ){
            tmp[i][j] = t[i][j];
            if( i == j ) ans[i][j] = 1;
            else ans[i][j] = 0;
        }
    base[0][0] = A * A % mol; base[1][0] = A; 
    base[2][0] = 1; base[3][0] = (1ll + A * A)%mol;
}

char s[100];

void solve()
{
    n -= 2;
    while( n > 0 )
    {
        if( n & 1 )
        {
            mult( ans, tmp );
        }
        mult( tmp, tmp );
        n >>= 1;
    }
//out( ans );
    mult( ans, base );
    u = ans[3][0];
    u %= mol;
    
    if( u < 0 )
        u += mol;
    //cout<<u<<endl;
    itoa( u, s, 10 );
    puts( s );
    //printf("%I64d\n",u);
}
    

int main()
{
    //freopen("tow1.in","r",stdin);
    //freopen("out.txt","w",stdout);
    int i, j, k;
    __int64 test;
    ch = getchar();
    in( test );
    while( test -- )
    {
        build();
        solve();
    }
    return 0;
}