#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p)
{
    int res = 1%p;
    while (b)
    {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    int m;
    cin>>m;
    while(m--)
    {
        int x,n,p;
        scanf("%d%d%d", &x, &n, &p);
        cout << qmi(x, n, p) << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p)
{
    int res = 1 % p;
    while (b)
    {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    int x, n;
    cin >> x >> n;
    cout << qmi(x, n, 233333) << endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1e4+10;

int f[N];
int a[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
            if(a[i]>a[j])
                f[i]=max(f[i],f[j]+1);
    }

    int res=0;
    for(int i=1;i<=n;i++)   res=max(res,f[i]);

    cout<<res<<endl;

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;


int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}


int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }

    return 0;
}

#include<iostream>
#include<algorithm>
#include<set>

#define x first
#define y second

using namespace std;

const int N = 1010;

typedef pair<int, int> PII;
int x0,y0;
int n;

int gcd(int a,int b)
{
    return b? gcd(b,a%b):a;
}

int main()
{
    cin>>n>>x0>>y0;

    int x,y;
    set<PII> S;

    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        x-=x0,y-=y0;
        int d=gcd(x,y);
        x/=d,y/=d;
        if(x<0) x=-x,y=-y;
        S.insert({x,y});

    }
    cout<<S.size()<<endl;

    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 50010;

int n,T;
int a[N],g[N],f[N];

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)   cin>>a[i];

        memset(f,-0x3f,sizeof f);
        memset(g,-0x3f,sizeof f);

        int s=0;
        for(int i=1;i<=n;i++)
        {
            s=max(0,s)+a[i];
            f[i]=max(f[i-1],s);
        }

        s=0;
        for(int i=n;i>=1;i--)
        {
            s=max(0,s)+a[i];
            g[i]=max(g[i+1],s);
        }

        int res=-0x3f3f3f3f;
        for(int i=1;i<n;i++)    res=max(res,f[i]+g[i+1]);

        cout<<res<<endl;
    }

    return 0;
}

#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;
const int N = 100010;

int n,m;
int a[N],s[11][N];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++)    scanf("%d", &a[i]);
    for(int i=0;i<n;i++)
    {
        LL t = a[i]%m;
        for(int j=0;j<11;j++)
        {
            s[j][t]++;
            t=t*10%m;
        }
    }

    LL res=0;
    for(int i=0;i<n;i++)
    {
        LL t=a[i]%m;
        int len=to_string(a[i]).size();
        res+=s[len][(m-t)%m];

        LL r=t;
        while(len--)    r=r*10%m;

        if(r==(-t+m)%m)  res--;
    }

    cout<<res<<endl;

    return 0;
}

#include<iostream>

using namespace std;

const int N = 110;

int n,m;
int f[N];
int v[N],w[N],s;

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        for(int j=0;j<s;j++)
            cin>>v[j]>>w[j];
        for(int j=m;j>=0;j--)//从大到小枚举使得所有情况只会被枚举一次 不会被组内物品多次更新
            for(int k=0;k<s;k++)
                if(j>=v[k])
                    f[j]=max(f[j],f[j-v[k]]+w[k]);
    }

    cout<<f[m]<<endl;

    return 0;

}

#include<iostream>

using namespace std;

const int N = 110;

int n,m;
int f[N];
int v[N],w[N],s;

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        for(int j=0;j<s;j++)
            cin>>v[j]>>w[j];
        for(int j=m;j>=0;j--)
            for(int k=0;k<s;k++)
                if(j>=v[k])
                    f[j]=max(f[j],f[j-v[k]]+w[k]);
    }

    cout<<f[m]<<endl;

    return 0;

}

#include<iostream>

using namespace std;

int n, v, u, w, f[1005];

int main() 
{
    cin >> n >> v;

    for (int i = 0; i < n; i++)
    {
        cin >> u >> w;
        for (int j = u; j <= v; j++)
            f[j] = max(f[j], f[j - u] + w);
    }

    cout << f[v] << endl;

    return 0;
}