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:
/*******************************************************************************
* author  : SuryanshPrabhat
* created : 22/12/2020 12:48
*******************************************************************************/
import java.io.IOException;
import java.io.PrintWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedOutputStream;
//import java.math.BigInteger;
import java.util.*;

public class b
{
    public static void main(String[] args)
    {
    	int T = in.nextInt();
    	while (T-- > 0)
    	{
            int n = in.nextInt();
            int[] arr = new int[n];
            long sum_odd = 0, sum = 0;
            for (int i = 1; i <= n; i++)
            {
                int num = in.nextInt();
                if ((i & 1) == 1)
                {
                    sum_odd += num;
                }
                sum += num;
                arr[i-1] = num;
            }
            boolean flag = (sum_odd <= sum/2);
            for (int i = 1; i <= n; i++)
            {
                if (flag)
                {
                    out.print("1 ");
                }
                else
                {
                    out.print(arr[i-1] + " ");
                }
                flag = !flag;
            }
            out.println();
    	}
        out.flush();
        out.close();
    }

    // Change Array type as necessary.
    static void printArray(int[] arr)
    {
        for (int i = 0; i < arr.length; i++)
        {
            out.print(arr[i] + " ");
        }
        out.println();
    }

    static int search(int[] arr, int target)
    {
        // ~ [lower_bound] & [upper_bound -> search for 1+target]
        int lo = 0, hi = arr.length-1;
        while (lo <= hi)
        {
            int mid = (lo+hi) >> 1;
            if (arr[mid] >= target)
            {
                hi = mid-1;
            }
            else
            {
                lo = mid+1;
            }
        }
        // Ensure existence for exact matches
        // if (lo == arr.length || arr[lo] != target)
        // {
        //     return -1;
        // }
        return lo;
    }

    static void sort(int[] arr)
    {
        // Random Shuffle guarantees O(nlogn) WCTC for Quick Sort.
        Random rnd = new Random();
        for (int i = arr.length-1; i > 0; i--)
        {
            swap(arr, i, rnd.nextInt(i));
        }
        // Dual-Pivot Quicksort Implementation
        Arrays.sort(arr);
    }

    static boolean[] sieve(int n)
    {
        boolean[] primes = new boolean[n+1];
        for (int i = 2; i <= n; i++)
        {
            if (i == 2 || ((i&1) == 1))
            {
                primes[i] = true;
            }
        }
        for (int p = 3; p*p <= n; p+=2)
        {
            if (primes[p] && 1l*p*p <= n)
            {
                for (int k = p*p; k <= n; k+=p)
                {
                    primes[k] = false;
                }
            }
        }
        return primes;
    }

    // MLE -> Use BitSet
    static BitSet bitsieve(int n)
    {
        BitSet primes = new BitSet(n+1);
        for (int i = 2; i <= n; i++)
        {
            if (i == 2 || ((i&1) == 1))
            {
                primes.set(i);
            }
        }
        for (int p = 3; p*p <= n; p+=2)
        {
            if (primes.get(p) && 1l*p*p <= n)
            {
                for (int k = p*p; k <= n; k+=p)
                {
                    primes.set(k, false);
                }
            }
        }
        return primes;
    }

    static void swap(int[] arr, int i, int j)
    {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    static void swap(int x, int y)
    {
        x = x ^ y;
        y = x ^ y;
        x = x ^ y;
    }

    // Precompute before running testcases
    static long[] fact;
    static void factorial(int lim)
    {
        fact = new long[lim];
        fact[0] = 1;
        for (int i = 1; i < lim; i++)
        {
            fact[i] = (fact[i-1]*i)%MOD;
        }
    }

    static long modInv(long x)
    {
        return pow(x, MOD-2, MOD);
    }

    static long modInv(long x, int MOD)
    {
        return pow(x, MOD-2, MOD);
    }

    static long perm(int n, int r)
    {
        // assert(fact != null);
        if (n < r)
        {
            return 0;
        }
        return (fact[n]*(modInv(fact[n-r])%MOD))%MOD;
    }

    static long comb(int n, int r)
    {
        // assert(fact != null);
        if (n < r)
        {
            return 0;
        }
        if (n == r)
        {
            return 1;
        }
        return (fact[n]*(((fact[r]%MOD)*(fact[n-r]%MOD))%MOD))%MOD;
    }

    static long pow(long x, long y)
    {
        //assert(y >= 0);
        if (x == 0)
        {
            return 0;
        }
        if (x == 1 || y == 0)
        {
            return 1;
        }
        long res = 1l;
        while (y > 1)
        {
            if ((y & 1) == 1)
            {
                res *= x;
            }
            x *= x;
            y >>= 1;
        }
        return res*x;
    }

    static long pow(long x, long y, int MOD)
    {
        //assert(y >= 0);
        if (x == 0)
        {
            return 0;
        }
        if (x == 1 || y == 0)
        {
            return 1;
        }
        // Use Math.floorMod or (MOD + res)%MOD
        // for handling negative x if necessary.
        x %= MOD;
        long res = 1l;
        while (y > 1)
        {
            if ((y&1) == 1)
            {
                res = (res*x)%MOD;
            }
            x = (x*x)%MOD;
            y >>= 1;
        }
        return (res*x)%MOD;
    }

    // Handle I/O
    static int MOD = (int)(1e9+7);
    static FastScanner in = new FastScanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static class FastScanner
    {
        BufferedReader br;
        StringTokenizer st;
        public FastScanner()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
            st = null;
        }

        String next()
        {
            while (st == null || !st.hasMoreTokens())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                        e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        int[] readIntArray(int size)
        {
            int[] arr = new int[size];
            for (int i = 0; i < size; i++)
            {
                arr[i] = nextInt();
            }
            return arr;
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        long[] readLongArray(int size)
        {
            long[] arr = new long[size];
            for (int i = 0; i < size; i++)
            {
                arr[i] = nextLong();
            }
            return arr;
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        double[] readDoubleArray(int size)
        {
            double[] arr = new double[size];
            for (int i = 0; i < size; i++)
            {
                arr[i] = nextDouble();
            }
            return arr;
        }
    }
}