#include <bits/stdc++.h>
using namespace std;
vector<vector<bool>> encode_good(int N, vector<vector<bool>> A){
  vector<bitset<2000>> B(N);
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      if (A[i][j]){
        B[i].set(j);
      }
    }
  }
  vector<bool> used(N, false);
  vector<vector<bool>> ans(N);
  vector<int> top(N);
  for (int i = 0; i < N; i++){
    for (int j = 0; j < i; j++){
      ans[i].push_back(B[i][top[j]]);
      if (B[i][top[j]]){
        B[i] ^= B[j];
      }
    }
    for (int j = 0; j < N; j++){
      if (!used[j]){
        ans[i].push_back(B[i][j]);
      }
    }
    for (int j = N - 1; j >= 0; j--){
      if (B[i][j]){
        top[i] = j;
        break;
      }
    }
    used[top[i]] = true;
  }
  return ans;
}
vector<vector<bool>> decode_good(int N, vector<vector<bool>> A){
  vector<bitset<2000>> B(N);
  vector<bool> used(N, false);
  for (int i = 0; i < N; i++){
    for (int j = 0; j < i; j++){
      if (A[i][j]){
        B[i] ^= B[j];
      }
    }
    int cnt = 0;
    for (int j = 0; j < N; j++){
      if (!used[j]){
        if (A[i][i + cnt]){
          B[i][j] = !B[i][j];
        }
        cnt++;
      }
    }
    for (int j = N - 1; j >= 0; j--){
      if (B[i][j]){
        used[j] = true;
        break;
      }
    }
  }
  vector<vector<bool>> ans(N, vector<bool>(N));
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      ans[i][j] = B[i][j];
    }
  }
  return ans;
}
vector<vector<bool>> encode_lucky(int N, vector<vector<bool>> A){
  vector<bool> used(N, false);
  vector<vector<bool>> ans(N);
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      if (used[j]){
        ans[i].push_back(A[i][j]);
      }
    }
    for (int j = 0; j < N; j++){
      if (!used[j]){
        ans[i].push_back(A[i][j]);
      }
    }
    for (int j = 0; j < N; j++){
      if (!used[j] && A[i][j]){
        used[j] = true;
        break;
      }
    }
  }
  return ans;
}
vector<vector<bool>> decode_lucky(int N, vector<vector<bool>> A){
  vector<bool> used(N, false);
  vector<vector<bool>> ans(N, vector<bool>(N, false));
  for (int i = 0; i < N; i++){
    int p = 0;
    for (int j = 0; j < N; j++){
      if (used[j]){
        ans[i][j] = A[i][p];
        p++;
      }
    }
    for (int j = 0; j < N; j++){
      if (!used[j]){
        ans[i][j] = A[i][p];
        p++;
      }
    }
    for (int j = 0; j < N; j++){
      if (!used[j] && A[i][j]){
        used[j] = true;
        break;
      }
    }
  }
  return ans;
}
int main(){
  int t;
  cin >> t;
  for (int i = 0; i < t; i++){
    string s;
    cin >> s;
    int n;
    cin >> n;
    vector<vector<bool>> A(n, vector<bool>(n));
    for (int j = 0; j < n; j++){
      string S;
      cin >> S;
      for (int k = 0; k < n; k++){
        A[j][k] = S[k] - '0';
      }
    }
    vector<vector<bool>> ans;
    if (s == "good"){
      ans = decode_lucky(n, encode_good(n, A));
    }
    if (s == "lucky"){
      ans = decode_good(n, encode_lucky(n, A));
    }
    for (int j = 0; j < n; j++){
      for (int k = 0; k < n; k++){
        cout << ans[j][k];
      }
      cout << endl;
    }
  }
}