#include <iostream>
using namespace std;
long long szybkie(long long a, long long b, long long p)
{
    a=a%p;
    long long a1=a*a;
    a1%=p;
    if (b<=1)
    return a;
    if (b%2==0)
        return szybkie(a1, b/2, p)%p;
    else
        return (szybkie(a1, b/2, p)*a)%p;
}
int main ()
{
    int n;
    cin >> n;
    for (int i=0; i<n; i++)
    {
        long long a, b, c, p;
        cin >> a >> b >> c >> p;
        if (a%p==0)
        {
            cout << 0 << "\n";
            continue;
        }
        long long x;
            x=szybkie(b, c, p);
        //cout << x << " ";
        cout << szybkie(a, x, p) << "\n";
    }
    return 0;
}