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.
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
#define  f               first
#define  s               second
#define  sym(s)          s = "#" + s + "#";
#define  all(x)          (x).begin(), (x).end()
#define  alll(x,n)       x+1, x+n+1
#define  newl            cout<<"\n";
#define  foo(i,a,n)      for(ll i = (a); i <= n; i++)
#define  deb1(a)         cout<<a<<"\n";
#define  deb2(a,b)       cout<<a<<" "<<b<<"\n";
#define  deb3(a,b,c)     cout<<a<<" "<<b<<" "<<c<<"\n";
#define  deb4(a,b,c,d)   cout<<a<<" "<<b<<" "<<c<<" "<<d<<"\n";
#define  debp(a)         cout<<a.f<<" "<<a.s<<"\n";
#define  debv(a)         for(auto it: a)cout<<it<<" ";newl;
#define  debm(a)         for(auto it: a)cout<<"{"<<it.f<<","<<it.s<<"}, ";newl;
#define  deb1d(a,n)      foo(i,1,n)cout<<a[i]<<" ";newl;
#define  deb2d(a,n,m)    foo(i,1,n){foo(j,1,m){cout<<a[i][j]<<" ";}newl;}

using namespace std;
using ll              =  long long;
using ld              =  long double;
const ll   MOD        =  1e+9 + 7;
const ll   INF        =  LLONG_MAX;
const int  N          =  (int)2e+5 + 8;

ll n;
string a[N], b[N];

void MAIN(int tc) {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        sym(a[i]);
    }
    a[0] = a[n + 1] = string(n + 2, '#');
    for (int i = 1; i <= n; i ++) {
        cin >> b[i];
        sym(b[i]);
    }
    b[0] = b[n + 1] = string(n + 2, '#');

    for (int j = 1; j <= n; j++) {
        if (a[1][j] != b[1][j]) {
            for (int i = 1; i <= n; i++) {
                a[i][j] = (a[i][j] == '1') ? '0' : '1';
            }
        }
    }
    for(int i = 2; i <= n; i++){
        int same = 1;
        for(int j = 1; j <= n; j++){
            same &=  (a[i][j] == b[i][j]);
        }
        if(same) continue;
        int comp = 1;
        for(int j = 1; j <= n; j++){
            comp &=  (a[i][j] != b[i][j]);
        }
        if(comp) continue;
        deb1("no");
        return;
    }
    deb1("yes");

}

int main() {
    ios:: sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout << fixed; cout << setprecision(10);

    int test_cases = 1;
    cin>>test_cases;
    for (int i = 1; i <= test_cases; i++) {
        MAIN(i);
    }
}