The only difference between the easy and hard versions is that tokens of type O do not appear in the input of the easy version.

Errichto gave Monogon the following challenge in order to intimidate him from taking his top contributor spot on Codeforces.

In a Tic-Tac-Toe grid, there are n rows and n columns. Each cell of the grid is either empty or contains a token. There are two types of tokens: X and O. If there exist three tokens of the same type consecutive in a row or column, it is a winning configuration. Otherwise, it is a draw configuration.

<image> The patterns in the first row are winning configurations. The patterns in the second row are draw configurations. 

In an operation, you can change an X to an O, or an O to an X. Let k denote the total number of tokens in the grid. Your task is to make the grid a draw in at most ⌊ k/3⌋ (rounding down) operations.

You are not required to minimize the number of operations.

Input

The first line contains a single integer t (1≤ t≤ 100) — the number of test cases.

The first line of each test case contains a single integer n (1≤ n≤ 300) — the size of the grid.

The following n lines each contain a string of n characters, denoting the initial grid. The character in the i-th row and j-th column is '.' if the cell is empty, or it is the type of token in the cell: 'X' or 'O'.

It is guaranteed that not all cells are empty.

In the easy version, the character 'O' does not appear in the input.

The sum of n across all test cases does not exceed 300.

Output

For each test case, print the state of the grid after applying the operations.

We have proof that a solution always exists. If there are multiple solutions, print any.

Example

Input


3
3
.X.
XXX
.X.
6
XX.XXX
XXXXXX
XXX.XX
XXXXXX
XX.X.X
XXXXXX
5
XXX.X
.X..X
XXX.X
..X..
..X..


Output


.X.
XOX
.X.
XX.XXO
XOXXOX
OXX.XX
XOOXXO
XX.X.X
OXXOXX
XOX.X
.X..X
XXO.O
..X..
..X..

Note

In the first test case, there are initially three 'X' consecutive in the second row and the second column. By changing the middle token to 'O' we make the grid a draw, and we only changed 1≤ ⌊ 5/3⌋ token.

In the second test case, we change only 9≤ ⌊ 32/3⌋ tokens, and there does not exist any three 'X' or 'O' consecutive in a row or column, so it is a draw.

In the third test case, we change only 3≤ ⌊ 12/3⌋ tokens, and the resulting grid is a draw.
import java.util.*;
import java.lang.*;
import java.io.*;  
public class Main 
{
/*
    HashMap<> map=new HashMap<>();
    TreeMap<> map=new TreeMap<>();
    map.put(p,map.getOrDefault(p,0)+1);
    for(Map.Entry<> mx:map.entrySet()){
          int v=mx.getValue(),k=mx.getKey();
    }
    ArrayList<Pair<Character,Integer>> l=new ArrayList<>();
    ArrayList<> l=new ArrayList<>();
    HashSet<> has=new HashSet<>();*/
    PrintWriter out;
    FastReader sc;
    int mod=(int)(1e9+7);
    HashSet<Long> h;
    void find(int l,int r,long[] sum,int[] ar){
          int mid=strSmall(l,r,ar,(ar[l]+ar[r])/2);
      //     pl(mid);
          if((mid)>=r||mid==-1)return;
          long k=(sum[mid]-sum[l])+ar[l],x=(sum[r]-sum[mid]);
      //     pl(k+" "+x);
          h.add(k);
          h.add(x);
          find(l,mid,sum,ar);
          find(mid+1,r,sum,ar);
    }
    public void sol(){
          int t=ni();
          while(t-->0){
                int n=ni();
                char[][] s=new char[n][n];
                for(int i=0;i<n;i++){
                      s[i]=rl();
                }int a1=0,a2=0,a3=0;
                for(int i=0;i<n;i++){
                      for(int j=0;j<n;j++){
                            if((i+j)%3==0&&s[i][j]=='X')a1++;
                            else if((i+j)%3==1&&s[i][j]=='X')a2++;
                            else if((i+j)%3==2&&s[i][j]=='X')a3++;
                      }
                }if(a1<=a2&&a1<=a3){
                      for(int i=0;i<n;i++){
                            for(int j=0;j<n;j++){
                                  if((i+j)%3==0&&s[i][j]=='X'){
                                        s[i][j]='O';
                                  }
                            }
                      }
                }else if(a2<=a1&&a2<=a3){
                      for(int i=0;i<n;i++){
                            for(int j=0;j<n;j++){
                                  if((i+j)%3==1&&s[i][j]=='X'){
                                        s[i][j]='O';
                                  }
                            }
                      }
                }else{
                      for(int i=0;i<n;i++){
                            for(int j=0;j<n;j++){
                                  if((i+j)%3==2&&s[i][j]=='X'){
                                        s[i][j]='O';
                                  }
                            }
                      }
                }StringBuilder sb=new StringBuilder();
                for(int i=0;i<n;i++){
                      for(int j=0;j<n;j++){
                            sb.append(s[i][j]);
                      }sb.append("\n");
                }pr(sb);
          }
    }
    public static void main(String[] args) 
	{ 
	      Main g=new Main();
		g.out=new PrintWriter(System.out);
		g.sc=new FastReader();
		g.sol();
		g.out.flush();
	}
	static class FastReader 
	{ 
		BufferedReader br; 
		StringTokenizer st; 
 
		public FastReader() 
		{ 
			br = new BufferedReader(new
					InputStreamReader(System.in)); 
		} 
 
		String next() 
		{ 
			while (st == null || !st.hasMoreElements()) 
			{ 
				try
				{ 
					st = new StringTokenizer(br.readLine()); 
				} 
				catch (IOException e) 
				{ 
					e.printStackTrace(); 
				} 
			} 
			return st.nextToken(); 
		} 
 
		int nextInt() 
		{ 
			return Integer.parseInt(next()); 
		} 
 
		long nextLong() 
		{ 
			return Long.parseLong(next()); 
		} 
 
		double nextDouble() 
		{ 
			return Double.parseDouble(next()); 
		} 
 
		String nextLine() 
		{ 
			String str = ""; 
			try
			{ 
				str = br.readLine(); 
			} 
			catch (IOException e) 
			{ 
				e.printStackTrace(); 
			} 
			return str; 
		} 
	} public int ni(){
	      return sc.nextInt();
	}public long nl(){
	      return sc.nextLong();
	}public double nd(){
	      return sc.nextDouble();
	}public char[] rl(){
	      return sc.nextLine().toCharArray();
	}public String rl1(){
	      return sc.nextLine();
	}
	public void pl(Object s){
	      out.println(s);
	}public void ex(){
	      out.println();
	}
	public void pr(Object s){
	      out.print(s);
	}public String next(){
	      return sc.next();
	}public long abs(long x){
	      return Math.abs(x);
	}
	public int abs(int x){
	      return Math.abs(x);
	}
	public double abs(double x){
	      return Math.abs(x);
	}
      public long pow(long x,long y){
            return (long)Math.pow(x,y);
      }
      public int pow(int x,int y){
            return (int)Math.pow(x,y);
      }
      public double pow(double x,double y){
            return Math.pow(x,y);
      }public long min(long x,long y){
            return (long)Math.min(x,y);
      }
      public int min(int x,int y){
            return (int)Math.min(x,y);
      }
      public double min(double x,double y){
            return Math.min(x,y);
      }public static int gcd(int a, int b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}static void sort(int[] a) {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i : a) {
			l.add(i);
		}
		Collections.sort(l);
		for (int i = 0; i < a.length; i++) {
			a[i] = l.get(i);
		}
	}void sort(long[] a) {
		ArrayList<Long> l = new ArrayList<>();
		for (long i : a) {
			l.add(i);
		}
		Collections.sort(l);
		for (int i = 0; i < a.length; i++) {
			a[i] = l.get(i);
		}
	}void sort(double[] a) {
		ArrayList<Double> l = new ArrayList<>();
		for (double i : a) {
			l.add(i);
		}
		Collections.sort(l);
		for (int i = 0; i < a.length; i++) {
			a[i] = l.get(i);
		}
	}int  swap(int a,int b){
	      return a;
	}long  swap(long a,long b){
	      return a;
	}double  swap(double a,double b){
	      return a;
	}
	boolean isPowerOfTwo (int x) 
      { 
            return x!=0 && ((x&(x-1)) == 0);     
      }boolean isPowerOfTwo (long x) 
      { 
            return x!=0 && ((x&(x-1)) == 0);     
      }public long max(long x,long y){
            return (long)Math.max(x,y);
      }
      public int max(int x,int y){
            return (int)Math.max(x,y);
      }
      public double max(double x,double y){
            return Math.max(x,y);
      }long sqrt(long x){
            return (long)Math.sqrt(x);
      }int sqrt(int x){
            return (int)Math.sqrt(x);
      }void input(int[] ar,int n){
            for(int i=0;i<n;i++)ar[i]=ni();
      }void input(long[] ar,int n){
            for(int i=0;i<n;i++)ar[i]=nl();
      }int maxint(){
            return Integer.MAX_VALUE;
      }int minint(){
            return Integer.MIN_VALUE;
      }long maxlong(){
            return Long.MAX_VALUE;
      }long minlong(){
            return Long.MIN_VALUE;
      }void fill(int[] ar,int k){
            Arrays.fill(ar,k);
      }void yes(){
            pl("YES");
      }void no(){
            pl("NO");
      }
    int[] sieve(int n) 
    { 
        boolean prime[] = new boolean[n+1]; 
        int[] k=new int[n+1];
        for(int i=0;i<=n;i++) {
            prime[i] = true; 
            k[i]=i;
        }
          
        for(int p = 2; p <=n; p++) 
        { 
            if(prime[p] == true) 
            { 
               // sieve[p]=p;
                for(int i = p*2; i <= n; i += p) {
                    prime[i] = false; 
                  //  sieve[i]=p;
                    while(k[i]%(p*p)==0){
                          k[i]/=(p*p);
                    }
                }
            } 
        }return k;
    }int strSmall(int start,int end,int[] arr, int target)  
    {  
      //   int start = 0, end = arr.length-1;  
        int ans = -1;  
        while (start <= end) {  
            int mid = (start + end) / 2;   
            if (arr[mid] > target) {  
                end = mid - 1;  
            }   
            else {  
                ans = mid;  
                start = mid + 1;  
            }  
        }  
        return ans;  
    } 
      public static class pair implements Comparable<pair> {
		int x;
		int y;
 
		public pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
 
		public String toString() {
			return x + "," + y;
		}
 
		public boolean equals(Object o) {
			if (o instanceof pair) {
				pair p = (pair) o;
				return p.x == x && p.y == y;
			}
			return false;
		}
 
		public int hashCode() {
			return new Double(x).hashCode() * 31 + new Double(y).hashCode();
		}
 
		public int compareTo(pair other) {
			if (this.x == other.x) {
				return Long.compare(this.y, other.y);
			}
			return Long.compare(this.x, other.x);
		}
      }
	 
} 