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 PYTHON3):

Solution:
T_ON = 1
DEBUG_ON = 0
MOD = 998244353


def solve():
    n = read_int()
    A = read_ints()
    odd = 0
    even = 0
    for i, x in enumerate(A):
        if i % 2:
            odd += x
        else:
            even += x
    B = A[:]
    for i in range(n):
        if odd < even and i % 2 == 1:
            B[i] = 1
        elif even <= odd and i % 2 == 0:
            B[i] = 1
    print_nums(B)


def solve2():
    A = read_ints()
    A.sort()
    a, b, c = A
    # (b-a) and (c-a) cannot be combined directly
    x = b - a + c - a
    q, r = divmod(x, 7)
    debug(a, b, c, x, q, r)
    a -= q
    if r:
        if (6-r) % 3 != 0:
            NO()
            return
        else:
            a -= (6-r) // 2 + 1
    if a >= 0 and a % 3 == 0:
        YES()
    else:
        NO()


def main():
    T = read_int() if T_ON else 1
    for i in range(T):
        solve()


def debug(*xargs):
    if DEBUG_ON:
        print(*xargs)


from collections import *


#---------------------------------FAST_IO---------------------------------------

import os
import sys
from io import BytesIO, IOBase
# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

#----------------------------------IO_WRAP--------------------------------------

def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split()))


def print_nums(nums):
    print(" ".join(map(str, nums)))


def YES():
    print("YES")


def Yes():
    print("Yes")


def NO():
    print("NO")


def No():
    print("No")

#----------------------------------FIB--------------------------------------

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


def fib_ns(n):
    assert n >= 1
    f = [0 for _ in range(n + 1)]
    f[0] = 0
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f

#----------------------------------MOD--------------------------------------

def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)


def xgcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        (q, a), b = divmod(b, a), a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0


def modinv(a, m):
    """return x such that (a * x) % m == 1"""
    g, x, _ = xgcd(a, m)
    if g != 1:
        raise Exception('gcd(a, m) != 1')
    return x % m


def mod_add(x, y):
    x += y
    while x >= MOD:
        x -= MOD
    while x < 0:
        x += MOD
    return x


def mod_mul(x, y):
    return (x * y) % MOD


def mod_pow(x, y):
    if y == 0:
        return 1
    if y % 2:
        return mod_mul(x, mod_pow(x, y - 1))
    p = mod_pow(x, y // 2)
    return mod_mul(p, p)


def mod_inv(y):
    return mod_pow(y, MOD - 2)


def mod_div(x, y):
    # y^(-1): Fermat little theorem, MOD is a prime
    return mod_mul(x, mod_inv(y))

#---------------------------------PRIME---------------------------------------

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i:
            return False
    return True


def gen_primes(n):
    """
    generate primes of [1..n] using sieve's method
    """
    P = [True for _ in range(n + 1)]
    P[0] = P[1] = False
    for i in range(int(n ** 0.5) + 1):
        if P[i]:
            for j in range(2 * i, n + 1, i):
                P[j] = False
    return P

#---------------------------------MAIN---------------------------------------

main()