#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

int f[][][][],g[][][][];

template<typename T>

void read(T &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void solve()

{

    long long n,m,k; int p;

    read(n); read(m); read(k); read(p);

    memset(f,,sizeof(f));

    memset(g,,sizeof(g));

    f[][][][]=;

    int A,B,C,z;

    int ni,mi,ki;

    for(int i=;i>=;--i)

        for(int a=;a<=;++a)

            for(int b=;b<=;++b)

                for(int c=;c<=;++c)

                    if(f[i+][a][b][c])

                    {

                        ni=n>>i&; mi=m>>i&; ki=k>>i&;

                        for(int x=;x<=;++x)

                            if(!a || x<=ni)

                                for(int y=;y<=;++y)

                                    if(!b || y<=mi)

                                    {

                                        z=x^y;

                                        if(c && z<ki) continue;

                                        A=a&x==ni; B=b&&y==mi; C=c&&z==ki;

                                        f[i][A][B][C]=(f[i][A][B][C]+f[i+][a][b][c])%p;

                                        g[i][A][B][C]=(g[i][A][B][C]+g[i+][a][b][c])%p;

                                        if(z) g[i][A][B][C]=(g[i][A][B][C]+(1LL<<i)%p*f[i+][a][b][c]%p)%p;

                                    }

                    }

    printf("%d\n",(g[][][][]-k%p*f[][][][]%p+p)%p);

}

int main()

{

    int T;

    read(T);

    while(T--) solve();

    return ;

}