Problem: You are given an array [a_1, a_2, ..., a_n] such that 1 ≤ a_i ≤ 10^9. Let S be the sum of all elements of the array a.

Let's call an array b of n integers beautiful if:

  * 1 ≤ b_i ≤ 10^9 for each i from 1 to n; 
  * for every pair of adjacent integers from the array (b_i, b_{i + 1}), either b_i divides b_{i + 1}, or b_{i + 1} divides b_i (or both); 
  * 2 ∑ _{i = 1}^{n} |a_i - b_i| ≤ S. 



Your task is to find any beautiful array. It can be shown that at least one beautiful array always exists.

Input

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

Each test case consists of two lines. The first line contains one integer n (2 ≤ n ≤ 50).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9).

Output

For each test case, print the beautiful array b_1, b_2, ..., b_n (1 ≤ b_i ≤ 10^9) on a separate line. It can be shown that at least one beautiful array exists under these circumstances. If there are multiple answers, print any of them.

Example

Input


4
5
1 2 3 4 5
2
4 6
2
1 1000000000
6
3 4 8 1 2 3


Output


3 3 3 3 3
3 6
1 1000000000
4 4 8 1 3 3

Solution (in JAVA):

Solution:
//note: 0<=|int|<= 2 * 10^9
//note: 0<=|long|<= 9 * 10^18
//note: 20! max w/ long
//note: 91st fibonacci # highest calculable w/long
//note: 0 <= |double| <= 1.8 * 10^308
//note: 170! max w/double;
//java machine can make 10^8 computations in a second.
import java.io.*;
import java.util.*;
import static java.lang.Math.max;
import static java.lang.Math.min;
    
public class CP{
    static int MAX = Integer.MAX_VALUE, MIN = Integer.MIN_VALUE;
    static FastScanner sc = new FastScanner();
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args){
    	solve();
        out.close();
    }
    
    static void solve() {
    	int t = sc.nextint();
    	while(t-->0) {
    		int n = sc.nextint();
    		int[] nums = sc.readint(n);
    		long sumOdd = 0, sumEven = 0;
    		for(int i = 0; i < n; ++i) {
    			if((i&1) == 0) {
    				sumEven += nums[i];
    			}
    			else {
    				sumOdd += nums[i];
    			}
    		}
    		if(sumOdd < sumEven) {
    			for(int i = 0; i < n; ++i) {
    				if((i&1) == 1) {
    					out.print(1 + " ");
    				}
    				else {
    					out.print(nums[i] + " ");
    				}
    			}
    		}
    		else {
    			for(int i = 0; i < n; ++i) {
    				if((i&1) == 0) {
    					out.print(1 + " ");
    				}
    				else {
    					out.print(nums[i] + " ");
    				}
    			}
    		}
    		out.println();
    	}
    }
    
    static class Pair{
    	int time, location;
    	public Pair(int time, int location) {
    		this.time = time;
    		this.location = location;
    	}
    }
    
    static class Node{
    	ArrayList<Node> adj = new ArrayList<>();
    	int id, sz;
    	public Node(int id) {
    		this.id = id;
    	}
    	void add(Node n) {
    		adj.add(n);
    	}
    }
    
    static class UnionFind{
        public int numComponents;
        public int[] sz, id;
        public UnionFind(int size) {
            numComponents = size;
            sz = new int[size];
            id = new int[size];
            for(int i = 0; i < size; ++i) {
                id[i] = i;
                sz[i] = 1;
            }
        }
        
        public int find(int p) {
            int root = p;
            while(root != id[root]) {
                root = id[root];
            }
            while(p != root) {
                int next = id[p];
                id[p] = root;
                p = next;
            }
            return root;
        }
        
        public void unify(int p, int q) {
            int root1 = find(p);
            int root2 = find(q);
            
            if(root1 == root2) {
                return;
            }
            
            if(sz[root1] < sz[root2]) {
                sz[root2] += sz[root1];
                id[root1] = id[root2];
            }
            else {
                sz[root1] += sz[root2];
                id[root2] = id[root1];
            }
                
            --numComponents;
        }
    }
    
    static class RMQ{
        int leftMost, rightMost, min, max;
        RMQ lChild, rChild;
        public RMQ(int lb, int rb, int[] a) {
            leftMost = lb;
            rightMost = rb;
            if(lb == rb) {
                min = max = a[lb];
                return;
            }
            int mb = (lb+rb)/2;
            lChild = new RMQ(lb, mb, a); 
            rChild = new RMQ(mb+1, rb, a);
            min = Math.min(lChild.min, rChild.min); 
            max = Math.max(lChild.max, rChild.max);
        }
        
        public void pointUpdate(int index, int val) {
            if(leftMost == rightMost) {
                min = val;
                max = val;
                return;
            }
            if(index <= lChild.rightMost) {
                lChild.pointUpdate(index, val);
            }
            else {
                rChild.pointUpdate(index, val);;
            }
            min = Math.min(lChild.min, rChild.min);
            max = Math.max(lChild.max, rChild.max);
        }
        
        public int rangeMin(int lb, int rb) {
            if(rightMost < lb || leftMost > rb) {
                return Integer.MAX_VALUE;
            }
            else if(rightMost <= rb && leftMost >= lb) {
                return min;
            }
            return Math.min(lChild.rangeMin(lb, rb), rChild.rangeMin(lb,rb));
        }
        
        public int rangeMax(int lb, int rb) {
            if(rightMost < lb || leftMost > rb) {
                return Integer.MIN_VALUE;
            }
            else if(rightMost <= rb && leftMost >= lb) {
                return max;
            }
            return Math.max(lChild.rangeMax(lb, rb), rChild.rangeMax(lb,rb));
        }
    }
    
    static long modInverse(long a, long b) {
        long bb = b, temp, q;
        long x0 = 0, x1 = 1;
        if(b == 1){
            return 1L;
        }
        while(a > 1){
            q = a/b;
            temp = b; b = a-(a/b)*b; a=temp;
            temp = x0; x0 = x1-q*x0; x1 = temp;
        }
        if(x1 < 0){
            x1 += bb;
        }
        return x1;
    }
    
    static long gcd(long a, long b) {
        if(a == 0) {
            return b;
        }
        return gcd(b%a, a);
    }
    
    static int gcd(int a, int b){
        if(a == 0){
            return b;
        }
        return gcd(b%a, a);
    }
    
    static BufferedReader br;
    static StringTokenizer st;
    
    static class FastScanner{
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int[] readint(int n) {
            int[] res = new int[n];
            for(int i = 0; i < n; i++) {
                res[i] = nextint();
            }
            return res;
        }
        long[] readlong(int n) {
            long[] res = new long[n];
            for(int i = 0; i < n; i++) {
                res[i] = nextlong();
            }
            return res;
        }
        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;
        }
    }
}