Problem: Artem is building a new robot. He has a matrix a consisting of n rows and m columns. The cell located on the i-th row from the top and the j-th column from the left has a value a_{i,j} written in it. 

If two adjacent cells contain the same value, the robot will break. A matrix is called good if no two adjacent cells contain the same value, where two cells are called adjacent if they share a side. 

Artem wants to increment the values in some cells by one to make a good.

More formally, find a good matrix b that satisfies the following condition — 

  * For all valid (i,j), either b_{i,j} = a_{i,j} or b_{i,j} = a_{i,j}+1. 



For the constraints of this problem, it can be shown that such a matrix b always exists. If there are several such tables, you can output any of them. Please note that you do not have to minimize the number of increments.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10). Description of the test cases follows.

The first line of each test case contains two integers n, m (1 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of rows and columns, respectively.

The following n lines each contain m integers. The j-th integer in the i-th line is a_{i,j} (1 ≤ a_{i,j} ≤ 10^9).

Output

For each case, output n lines each containing m integers. The j-th integer in the i-th line is b_{i,j}.

Example

Input


3
3 2
1 2
4 5
7 8
2 2
1 1
3 3
2 2
1 3
2 2


Output


1 2
5 6
7 8
2 1
4 3
2 4
3 2

Note

In all the cases, you can verify that no two adjacent cells have the same value and that b is the same as a with some values incremented by one. 

Solution (in JAVA):

Solution:
import java.util.*;
import java.math.*;
import java.io.*; 
 public class A{

static FastReader scan=new FastReader();
  public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
  static LinkedList<Integer>edges[];
  static LinkedList<Integer>Same[];
  static LinkedList<Integer>Dif[];
  static LinkedList<Integer>integers[];
static int []dx={1,-1,0,0};
static int []dy={0,0,1,-1};
int dx_8[]={1,1,1,0,0,-1,-1,-1};
int dy_8[]={-1,0,1,-1,1,-1,0,1};
static int n,m;
static boolean prime[];
static long LCM(long a,long b){
    return (Math.abs(a*b))/gcd(a,b);
   }
   static long gcd(long a, long b) {
    if(a!=0&&b!=0)
        while((a%=b)!=0&&(b%=a)!=0);
    return a^b;
}
static int countSetBits(int n) 
    { 
        int count = 0; 
        while (n > 0) { 
            count += n & 1; 
            n >>= 1; 
        } 
        return count; 
    } 
 static void sieve(long n) 
    { 
        
        prime = new boolean[(int)n+1]; 
        for(int i=0;i<n;i++) 
            prime[i] = true; 
          
        for(int p = 2; p*p <=n; p++) 
        { 
           
            if(prime[p] == true) 
            { 
                
                for(int i = p*p; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
    }  
    
    static int count;
 
  static boolean canTransmit[][]=new boolean[1000+5][1000+5];

    
    
    static boolean vis[][];
    static int color[]=new int[(int)1e5+5];
   static long cnt[]=new long[2];
static boolean bad=false;
    static void dfs(int v,int col){
        
        color[v]=col;
        for(int i:Dif[v])
        {
            if(~color[i]!=0)
            {
                if(color[i]==color[v])
                    bad=true;
                
            }
            else dfs(i,col^1);
        }
 for(int i:Same[v])
        {
            if(~color[i]!=0)
            {
                if(color[i]==(color[v]^1))
                    bad=true;
                
            }
            else dfs(i,col);
        }
            }
            static char grid[][];
            static char copy[][];
            static int N;
            static boolean e(int x,int y){
                return(x>=0&&x<N&&y>=0&&y<N);
            }
         
           static boolean isprime(long x)
           {
            for(long i=2;i*i<=x;i++)
                if(x%i==0)
                    return false;
                return true;
           }
           static boolean visisted[]=new boolean[(int)1e5+5];
           static int c[]=new int[(int)1e5+5];
           static int contain[]=new int[(int)1e5+5];
           static int ans=0;
           static void dfs_(int v){
            visisted[v]=true;
            if(c[v]>m){
               // out.println(v);
               return;
            }
            int cnt=0;
          for(int i:edges[v])
          {
            //contain[i]=contain[v];
            if(visisted[i])
                continue;
           c[i]=c[v]+1;
           if(contain[i]==0)c[i]=0;
                dfs_(i);
                cnt++;
          }
          if(cnt==0){
        //out.println(v);
            ans++;
        }
           }

public static void main(String[] args)  throws IOException 
{
//java.util.Scanner scan=new java.util.Scanner(new File("revegetate.in"));
 //PrintWriter out = new PrintWriter (new FileWriter("revegetate.out"));
  //  System.out.println(~-1);
    

        //System.out.println(0^1);

//SUCK IT UP AND DO IT ALRIGHT
    //System.out.println(true|true);
 int t=scan.nextInt();
 while(t-->0)
 {
    int n=scan.nextInt(),m=scan.nextInt();
    int tmp[][]=new int[n][m];
    
    int arr[][]=new int[n][m];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            arr[i][j]=scan.nextInt();
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(((i+j)%2==1&&arr[i][j]%2==0)||((i+j)%2==0&&arr[i][j]%2==1))
                 arr[i][j]++;




           }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            out.print(arr[i][j]+" ");
        out.println();
    }
 }
out.close();
//SEE UP 

}
static long powMod(long base, long exp, long mod) {
       if (base == 0 || base == 1) return base;
       if (exp == 0) return 1;
       if (exp == 1) return base % mod;
       long R = powMod(base, exp/2, mod) % mod;
       R *= R;
       R %= mod;
       if ((exp & 1) == 1) {
           return base * R % mod;
       }
       else return R % mod;
   }
static double dis(double x1,double y1,double x2,double y2)
{
    return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
static long mod(long x,long y)
    {
        if(x<0)
            x=x+(-x/y+1)*y;
        return x%y;
    }
 public static  long pow(long b, long e) {
            long r = 1;
            while (e > 0) {
                if (e % 2 == 1) r = r * b ;
                b = b * b;
                e >>= 1;
            }
            return r;
        }
private static void sort(long[] arr) {
        List<Long> list = new ArrayList<>();
        for (long object : arr) list.add(object);
        Collections.sort(list);
        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
    }
 public static class FastReader {
        BufferedReader br;
        StringTokenizer root;
        
 
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        boolean hasNext(){
            String line;
            while(root.hasMoreTokens())
                return true;
            return false;
        }
 
        String next() {
            while (root == null || !root.hasMoreTokens()) {
                try {
                    root = new StringTokenizer(br.readLine());
                } catch (Exception addd) {
                    addd.printStackTrace();
                }
            }
            return root.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (Exception addd) {
                addd.printStackTrace();
            }
            return str;
        }
         public int[] nextIntArray(int arraySize) {
            int array[] = new int[arraySize];
 
            for (int i = 0; i < arraySize; i++) {
                array[i] = nextInt();
            }
 
            return array;
        }
}
 static class Pair implements Comparable<Pair>{
        public int x, y;
        public Pair(int x1, int y1) {
            x=x1;
            y=y1;
        }
        @Override
        public int hashCode() {
            return (int)(x + 31 * y);
        }
        public String toString() {
            return x + " " + y;
        }
        @Override
        public boolean equals(Object o){
            if (o == this) return true;
            if (o.getClass() != getClass()) return false;
            Pair t = (Pair)o;
            return t.x == x && t.y == y;
        }
public int compareTo(Pair o)
{
    return (x-o.y)-(o.x-y);

    }

static class pair{
    int i;
    int j;
pair(int i,int j){
    this.i=i;
    this.j=j;
}}}
 static class tuple{
        int x,y,z;
        tuple(int a,int b,int c){
            x=a;
            y=b;
            z=c;
        }
    }
    static class Edge{
        int d,w;
        Edge(int d,int w)
        {
            this.d=d;
            this.w=w;
        }
    }
}