#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + ;

typedef long long ll;

bool flag[maxn]; //标记数组

ll phi[maxn]; //欧拉函数值

int prime[maxn]; //同时得到素数筛

int cnt = ;

void Get_phi(int n)

{

    cnt = ;

    memset(flag,true,sizeof(flag));

    phi[] = ;

    for(int i=;i<=n;i++)

    {

        if(flag[i]) //素数

        {

            prime[cnt++] = i;

            phi[i] = i-; //素数的欧拉函数值是i-1

        }

        for(int j=;j<cnt;j++)

        {

            if(i*prime[j]>n)

            {

                break;

            }

            flag[i*prime[j]] = false;//素数的倍数不是素数

            if(i%prime[j]==) //i%mod prime = 0,那么phi(i*p) = p*phi(i)

            {

                phi[i*prime[j]] = prime[j]*phi[i];

                break;

            }

            else phi[i*prime[j]] = (prime[j]-)*phi[i];//i mod prime != 0, 那么 phi(i * prime) == phi(i) * (prime-1)

        }

    }

}

int inv[maxn];

ll f[maxn];

int main()

{

    int T; scanf("%d", &T);

    Get_phi(1e6 + );

    while(T--)

    {

        int n, m, mod; scanf("%d %d %d", &n, &m, &mod);

        if(n > m) swap(n, m);

        inv[] = inv[] = ;

        for(int i = ; i <= n; i++)

        {

            inv[i] = (ll)(mod - mod / i) * inv[mod % i] % (ll)mod;

        }

        ll ans = ;

        for(int i = n; i >= ; i--) ///枚举 d | (a, b)

        {

            f[i] = (ll)n / i * (m / i);

            for(int j = i + i; j <= n; j += i) ///枚举 能够整除d的

            {

                f[i] = f[i] - f[j];

            }

            ans = (ans + f[i] * i % mod * inv[phi[i]]) % mod;

            //printf("%d %lld phi = %lld %lld\n", i, f[i], phi[i], ans);

        }

        printf("%lld\n", ans);

    }

    return ;

}

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + ;

inline char nc(){

    static char buf[],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;

}

inline int _read(){

    char ch=nc();int sum=;

    while(!(ch>=''&&ch<=''))ch=nc();

    while(ch>=''&&ch<='')sum=sum*+ch-,ch=nc();

    return sum;

}

struct node

{

    int a[];

    int b[];

};

node cur[maxn];

struct single

{

    int val, id;

    friend bool operator < (single A, single B)

    {

        return A.val > B.val;

    }

};

priority_queue<single> q[];

int v[];

int main()

{

    int T; T = _read();

    while(T--)

    {

        int n, k;

        n = _read(), k = _read();

       // printf("%d %d\n", n, k);

        for(int i = ; i <= k; i++) v[i] = _read();

        for(int i = ; i <= k; i++)

        {

            while(!q[i].empty()) q[i].pop();

        }

        for(int i = ; i <= n; i++)

        {

            for(int j = ; j <= k; j++) cur[i].a[j] = _read();

            for(int j = ; j <= k; j++) cur[i].b[j] = _read();

            q[].push({cur[i].a[], i});

        }

        int flag = ;

        int ans = ;

        while()

        {

            flag = ;

            for(int i = ; i <= k; i++)

            {

                if(q[i].empty()) continue;

                single tmp = q[i].top();

                if(tmp.val <= v[i])

                {

                    flag = ;

                    q[i].pop();

                    if(i == k)

                    {

                        ans++;

                        for(int j = ; j <= k; j++)

                        {

                            v[j] += cur[tmp.id].b[j];

                        }

                    }

                    else

                    {

                        q[i + ].push({cur[tmp.id].a[i + ], tmp.id});

                    }

                }

            }

            if(!flag) break;

        }

        printf("%d\n", ans);

        for(int i = ; i <= k; i++)

        {

            printf("%d%c", v[i], i < k ? ' ' : '\n');

        }

    }

    return ;

}