#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int __int128
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int N = 10000 + 5 ; 
int T, n, m, P, st[N], top, w[N], num, c[N] ; 
int mul( int a, int b, int p ) {
    return ( a % p ) * ( b % p ) % p ;  
}
int fpow( int x, int k, int p ) {
    int ans = 1, base = x % p ; 
    while( k ) {
        if( k & 1 ) ans = mul( ans, base, p ) ;
        base = mul( base, base, p ), k >>= 1 ; 
    } return ans % p ; 
}
bool M_R( int p ) {
    if( p == 2 || p == 3 ) return 1 ; 
    if( p == 1 || ( p % 2 == 0 ) ) return 0 ; 
    re int d = p - 1, s = 0 ; while( !( d & 1 ) ) ++ s, d >>= 1 ; 
    rep( i, 0, 5 ) {
        re int a = rand() % ( p - 3 ) + 2 ; 
        re int x = fpow( a, d, p ), y = 0 ;
        for( register int j = 0; j < s; ++ j ) {
            y = mul( x, x, p ) ; if( y == 1 && ( x != 1 ) && x != ( p - 1 ) ) return 0 ;
            x = y ;
        } if( y != 1 ) return 0 ;
    } return 1 ; 
}
int gcd( int x, int y ) {
    return ( x == 0 ) ? y : gcd( y % x, x ) ;
}
int Rand( int x ) {
    return 1ll * ((rand() << 15 ^ rand()) << 30 ^ (rand() << 15 ^ rand())) % x ; //2
}
int work( int p ) {
    re int k = 2, x = Rand(p - 1) + 1, y = x, d = 1, c = Rand(p) % 999997 ;
    for( re int i = 1; d == 1; ++ i ) {
        x = ( mul( x, x, p ) + c ) % p ;
        d = gcd( (x > y) ? x - y : y - x, p ) ;
        if( i == k ) y = x, k <<= 1 ; 
    } return d ; 
}
void Pollard_Rho(int p) {
    if( p == 1 ) return ; 
    if( M_R(p) ) { st[++ top] = p; return ; }
    int x = p ; while( x == p ) x = work(x) ;
    Pollard_Rho(x), Pollard_Rho(p / x) ;
}
int Ans = 0 ;
void dfs( int x, int f, int d, int p ) {
    if( x == num + 1 ) {
        if( ( (d & 1) ) && ( !( (n / d) & 1 ) ) ) return ;
        int g = ( d & 1 ) ? d : d / 2 ;
        Ans = ( Ans + mul( mul( fpow( m, ( d + 1 ) / 2, p ), g, p ), (f + p) % p, p ) + p ) % p ;
        return ; 
    }
    int fd = 1 ; 
    rep( i, 0, c[x] ) {
        if( i == c[x] ) dfs( x + 1, f, d * fd, p ) ;
        else dfs( x + 1, f * ( 1 - w[x] ), d * fd, p ) ;
        fd = fd * w[x] ; 
    }
}
signed main()
{
    srand(time(NULL)) ; 
    T = gi() ; 
    while( T-- ) {
        n = gi(), m = gi(), P = gi(), top = 0, num = 0, Ans = 0 ;
        memset( c, 0, sizeof(c) ), memset( w, 0, sizeof(w) ), memset( st, 0, sizeof(st) ) ;
        Pollard_Rho(n) ; 
        sort( st + 1, st + top + 1 ) ;
        rep( i, 1, top ) {
            if( st[i] == st[i - 1] ) ++ c[num] ; 
            else w[++ num] = st[i], c[num] = 1 ; 
        }
        dfs( 1, 1, 1, P ) ;
        printf("%lld\n", (long long)((Ans) % P) ) ;
    }
    return 0 ;
}

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int __int128
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int N = 10000 + 5 ; 
int T, n, m, P, st[N], top, w[N], num, c[N] ; 
int mul( int a, int b, int p ) {
    return ( a % p ) * ( b % p ) % p ;  
}
int fpow( int x, int k, int p ) {
    int ans = 1, base = x % p ; 
    while( k ) {
        if( k & 1 ) ans = mul( ans, base, p ) ;
        base = mul( base, base, p ), k >>= 1 ; 
    } return ans % p ; 
}
bool M_R( int p ) {
    if( p == 2 || p == 3 ) return 1 ; 
    if( p == 1 || ( p % 2 == 0 ) ) return 0 ; 
    re int d = p - 1, s = 0 ; while( !( d & 1 ) ) ++ s, d >>= 1 ; 
    rep( i, 0, 5 ) {
        re int a = rand() % ( p - 3 ) + 2 ; 
        re int x = fpow( a, d, p ), y = 0 ;
        for( register int j = 0; j < s; ++ j ) {
            y = mul( x, x, p ) ; if( y == 1 && ( x != 1 ) && x != ( p - 1 ) ) return 0 ;
            x = y ;
        } if( y != 1 ) return 0 ;
    } return 1 ; 
}
int gcd( int x, int y ) {
    return ( x == 0 ) ? y : gcd( y % x, x ) ;
}
int Rand( int x ) {
    return 1ll * ((rand() << 15 ^ rand()) << 30 ^ (rand() << 15 ^ rand())) % x ; //2
}
int work( int p ) {
    re int k = 2, x = Rand(p - 1) + 1, y = x, d = 1, c = Rand(p) % 999997 ;
    for( re int i = 1; d == 1; ++ i ) {
        x = ( mul( x, x, p ) + c ) % p ;
        d = gcd( (x > y) ? x - y : y - x, p ) ;
        if( i == k ) y = x, k <<= 1 ; 
    } return d ; 
}
void Pollard_Rho(int p) {
    if( p == 1 ) return ; 
    if( M_R(p) ) { st[++ top] = p; return ; }
    int x = p ; while( x == p ) x = work(x) ;
    Pollard_Rho(x), Pollard_Rho(p / x) ;
}
int Ans = 0 ;
void dfs( int x, int f, int d, int p ) {
    if( x == num + 1 ) {
        if( ( (d & 1) ) && ( !( (n / d) & 1 ) ) ) return ;
        int g = ( d & 1 ) ? d : d / 2 ;
        Ans = ( Ans + mul( mul( fpow( m, ( d + 1 ) / 2, p ), g, p ), (f + p) % p, p ) + p ) % p ;
        return ; 
    }
    int fd = 1 ; 
    rep( i, 0, c[x] ) {
        if( i == c[x] ) dfs( x + 1, f, d * fd, p ) ;
        else dfs( x + 1, f * ( 1 - w[x] ), d * fd, p ) ;
        fd = fd * w[x] ; 
    }
}
signed main()
{
    srand(time(NULL)) ; 
    T = gi() ; 
    while( T-- ) {
        n = gi(), m = gi(), P = gi(), top = 0, num = 0, Ans = 0 ;
        memset( c, 0, sizeof(c) ), memset( w, 0, sizeof(w) ), memset( st, 0, sizeof(st) ) ;
        Pollard_Rho(n) ; 
        sort( st + 1, st + top + 1 ) ;
        rep( i, 1, top ) {
            if( st[i] == st[i - 1] ) ++ c[num] ; 
            else w[++ num] = st[i], c[num] = 1 ; 
        }
        dfs( 1, 1, 1, P ) ;
        printf("%lld\n", (long long)((Ans) % P) ) ;
    }
    return 0 ;
}