inline bool MillerRabinTest( ll n, int k ) {
    if ( n <= 3 ) return true;
    if ( n % 2 == 0 ) return false;
    ll t = n - 1;
    ll s = 0;

    while ( t % 2 == 0 ) {
        t /= 2;
        s += 1;
    }
    for ( int i = 0; i < k; i++ ) {
        ll a = rnd( 2LL, n - 2 );
        ll x = binpow( a, t, n );
        if ( x == 1 || x == n - 1 ) {
            continue;
        }

        for ( int r = 1; r < s; r++ ) {
            x = binmul( x, x, n );

            if ( x == 1 ) return false;

            if ( x == n - 1 ) break;
        }
        if ( x != n - 1 ) return false;
    }
    return true;
}


inline ll polard( ll n ) {
    ll x = rnd( 2LL, n - 2 );
    ll i = 0, stage = 2, y = 1;

    while ( true ) {
        if ( i == stage ) {
            y = x;
            stage *= 2;
        }
        x = binmul( x, x, n ) + 1;
        x %= n;
        i++;
        ll d = gcd( x > y ? x - y : y - x, n );
        if ( d != 1 && d != n ) {
            return d;
        }
    }
}