You are given two binary square matrices a and b of size n × n. A matrix is called binary if each of its elements is equal to 0 or 1. You can do the following operations on the matrix a arbitrary number of times (0 or more): 

  * vertical xor. You choose the number j (1 ≤ j ≤ n) and for all i (1 ≤ i ≤ n) do the following: a_{i, j} := a_{i, j} ⊕ 1 (⊕ — is the operation [xor](https://en.wikipedia.org/wiki/Exclusive_or) (exclusive or)). 
  * horizontal xor. You choose the number i (1 ≤ i ≤ n) and for all j (1 ≤ j ≤ n) do the following: a_{i, j} := a_{i, j} ⊕ 1. 



Note that the elements of the a matrix change after each operation.

For example, if n=3 and the matrix a is: $$$ \begin{pmatrix} 1 & 1 & 0 \\\ 0 & 0 & 1 \\\ 1 & 1 & 0 \end{pmatrix} $$$ Then the following sequence of operations shows an example of transformations: 

  * vertical xor, j=1. $$$ a= \begin{pmatrix} 0 & 1 & 0 \\\ 1 & 0 & 1 \\\ 0 & 1 & 0 \end{pmatrix} $$$ 
  * horizontal xor, i=2. $$$ a= \begin{pmatrix} 0 & 1 & 0 \\\ 0 & 1 & 0 \\\ 0 & 1 & 0 \end{pmatrix} $$$ 
  * vertical xor, j=2. $$$ a= \begin{pmatrix} 0 & 0 & 0 \\\ 0 & 0 & 0 \\\ 0 & 0 & 0 \end{pmatrix} $$$ 



Check if there is a sequence of operations such that the matrix a becomes equal to the matrix b.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases. Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 1000) — the size of the matrices.

The following n lines contain strings of length n, consisting of the characters '0' and '1' — the description of the matrix a.

An empty line follows.

The following n lines contain strings of length n, consisting of the characters '0' and '1' — the description of the matrix b.

It is guaranteed that the sum of n over all test cases does not exceed 1000.

Output

For each test case, output on a separate line: 

  * "YES", there is such a sequence of operations that the matrix a becomes equal to the matrix b; 
  * "NO" otherwise. 



You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

Example

Input


3
3
110
001
110

000
000
000
3
101
010
101

010
101
010
2
01
11

10
10


Output


YES
YES
NO

Note

The first test case is explained in the statements.

In the second test case, the following sequence of operations is suitable: 

  * horizontal xor, i=1; 
  * horizontal xor, i=2; 
  * horizontal xor, i=3; 



It can be proved that there is no sequence of operations in the third test case so that the matrix a becomes equal to the matrix b.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,a,b,c) for(ll i=a;i<b;i+=c)
#define For2(i,a,b,c) for(ll i=a;i>=b;i-=c)
#define vec_ll vector<vector<ll>>
#define vec_pr vector<pair<ll,ll>>
#define pr pair<ll,ll>
#define pbk push_back
#define mkpr make_pair
#define fst first
#define snd second

void print(ll *arr, ll n){
    For(i,0,n,1)cout<<arr[i]<<" ";
    cout<<endl;
}


bool s_sec(const pair<ll,ll> &a, const pair<ll,ll> &b) {
    return (a.second < b.second);
}

ll fast_expo(ll a, ll p){
    //cout<<a<<" ";
    ll x=p-2;
    ll curr=a;
    ll ans=1;
    while(x!=0){
        if(x%2==1){
            ans=(ans*curr)%p;
        }
        x/=2;
        curr=(curr*curr)%p;
    }
    return ans;
}

bool solve(vec_ll &mat_xor, ll n){
    bool horiz=true, vert=true;

    For(i,0,n,1){
        ll sum=0, sum2=0;

        For(j,0,n,1){
            sum+=mat_xor[i][j];
            sum2+=mat_xor[j][i];
        }

        if(n>sum && sum>0){
            horiz=false;
        }

        if(n>sum2 && sum2>0){
            vert=false;
        }
    }

    if(horiz==true || vert==true){
        return true;
    }
    else{
        ll arr1[n][n];

        bool poss=true;
        For(i,0,n,1){
            arr1[0][i]=mat_xor[0][i];
        }

        ///First check whether arr1 can be made equal to mat_xor
        For(i,1,n,1){
            arr1[i][0]=mat_xor[i][0];
            ll temp=(arr1[i][0]+mat_xor[0][0])%2;

            For(j,1,n,1){
                arr1[i][j]=(arr1[0][j] xor temp);
            }
        }

        For(i,0,n,1){
            For(j,0,n,1){
                poss = poss && (arr1[i][j] == mat_xor[i][j]);
            }
        }

        return poss;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    /*ll T,p=1000000007;
    cin>>T;

    ll fact[1001],inverse[1001];
    fact[0]=fact[1]=inverse[0]=inverse[1]=1;

    For(i,2,1001,1){
        fact[i]=(fact[i-1]*i)%p;
        inverse[i]=fast_expo(fact[i],p);
    }*/

    ll T;
    cin>>T;

    while(T--){
        ll n;
        cin>>n;

        string a[n],b[n];

        ///
        For(i,0,n,1){
            cin>>a[i];
        }

        ///
        For(i,0,n,1){
            cin>>b[i];
        }

        vec_ll mat_xor;
        For(i,0,n,1){
            vector<ll> temp;
            For(j,0,n,1){
                temp.pbk((a[i][j]-'0' + b[i][j]-'0')%2);
            }
            mat_xor.pbk(temp);
        }

        bool poss=solve(mat_xor,n);
        if(poss==true){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
}
