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:
#!/usr/bin/env python
from __future__ import division, print_function
import math
import os
import sys
from fractions import *
from sys import *
from io import BytesIO, IOBase
from itertools import *
from collections import *
# sys.setrecursionlimit(10**5)



if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
# sys.setrecursionlimit(10**6)

# 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")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

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

def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input

def out(var): sys.stdout.write(str(var))  # for fast output, always take string

def lis(): return list(map(int, inp().split()))

def stringlis(): return list(map(str, inp().split()))

def sep(): return map(int, inp().split())

def strsep(): return map(str, inp().split())

def fsep(): return map(float, inp().split())

def inpu(): return int(inp())
# -----------------------------------------------------------------

def regularbracket(t):
    p = 0
    for i in t:
        if i == "(":
            p += 1
        else:
            p -= 1
        if p < 0:
            return False
    else:
        if p > 0:
            return False
        else:
            return True


# -------------------------------------------------
def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left) / 2)

        # Check if middle element is
        # less than or equal to key
        if (arr[mid] <= key):
            count = mid + 1
            left = mid + 1
         # If key is smaller, ignore right half
        else:
            right = mid - 1
    return count


# ------------------------------reverse string(pallindrome)
def reverse1(string):
    pp = ""
    for i in string[::-1]:
        pp += i
    if pp == string:
        return True
    return False


# --------------------------------reverse list(paindrome)
def reverse2(list1):
    l = []
    for i in list1[::-1]:
        l.append(i)
    if l == list1:
        return True
    return False


def mex(list1):
    # list1 = sorted(list1)
    p = max(list1) + 1
    for i in range(len(list1)):
        if list1[i] != i:
            p = i
            break
    return p


def sumofdigits(n):
    n = str(n)
    s1 = 0
    for i in n:
        s1 += int(i)
    return s1


def perfect_square(n):
    s = math.sqrt(n)
    if s == int(s):
        return True
    return False


# -----------------------------roman
def roman_number(x):
    if x > 15999:
        return
    value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbol = ["F", "MF", "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    roman = ""
    i = 0
    while x > 0:
        div = x // value[i]
        x = x % value[i]
        while div:
            roman += symbol[i]
            div -= 1
        i += 1
    return roman


def soretd(s):
    for i in range(1, len(s)):
        if s[i - 1] > s[i]:
            return False
    return True


# print(soretd("1"))
# ---------------------------
def countRhombi(h, w):
    ct = 0
    for i in range(2, h + 1, 2):
        for j in range(2, w + 1, 2):
            ct += (h - i + 1) * (w - j + 1)
    return ct


def countrhombi2(h, w):
    return ((h * h) // 4) * ((w * w) // 4)


# ---------------------------------
def binpow(a, b):
    if b == 0:
        return 1
    else:
        res = binpow(a, b // 2)
    if b % 2 != 0:
        return res * res * a
    else:
        return res * res

# -------------------------------------------------------
def binpowmodulus(a, b, m):
    a %= m
    res = 1
    while (b > 0):
        if (b & 1):
            res = res * a % m
        a = a * a % m
        b >>= 1
    return res

# -------------------------------------------------------------
def coprime_to_n(n):
    result = n
    i = 2
    while (i * i <= n):
        if (n % i == 0):
            while (n % i == 0):
                n //= i
            result -= result // i
        i += 1
    if (n > 1):
        result -= result // n
    return result

# -------------------prime
def prime(x):
    if x == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            #print(x)
            if (x % i == 0):
                return False
        else:
            return True

def luckynumwithequalnumberoffourandseven(x, n, a):
    if x >= n and str(x).count("4") == str(x).count("7"):
        a.append(x)
    else:
        if x < 1e12:
            luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
            luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
    return a

def luckynuber(x, n, a):
    p = set(str(x))
    if len(p) <= 2:
        a.append(x)
    if x < n:
        luckynuber(x + 1, n, a)
    return a
#------------------------------------------------------interactive problems

def interact(type, x):
    if type == "r":
        inp = input()
        return inp.strip()
    else:
        print(x, flush=True)

#------------------------------------------------------------------zero at end of factorial of a number
def findTrailingZeros(n):
    # Initialize result
    count = 0

    # Keep dividing n by
    # 5 & update Count
    while (n >= 5):
        n //= 5
        count += n

    return count
#-----------------------------------------------merge sort
# Python program for implementation of MergeSort
def mergeSort(arr):
    if len(arr) > 1:

        # Finding the mid of the array
        mid = len(arr) // 2

        # Dividing the array elements
        L = arr[:mid]

        # into 2 halves
        R = arr[mid:]

        # Sorting the first half
        mergeSort(L)

        # Sorting the second half
        mergeSort(R)

        i = j = k = 0

        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
#-----------------------------------------------lucky number with two lucky any digits
res = set()
def solven(p, l, a, b,n):#given number
    if p > n or l > 10:
        return
    if p > 0:
        res.add(p)
    solven(p * 10 + a, l + 1, a, b,n)
    solven(p * 10 + b, l + 1, a, b,n)
# problem
"""
n = int(input())
for a in range(0, 10):
    for b in range(0, a):
        solve(0, 0)
print(len(res))
"""

# Python3 program to find all subsets
# by backtracking.

# In the array A at every step we have two
# choices for each element either we can
# ignore the element or we can include the
# element in our subset
def subsetsUtil(A, subset, index,d):
    print(*subset)
    s = sum(subset)
    d.append(s)
    for i in range(index, len(A)):
        # include the A[i] in subset.
        subset.append(A[i])

        # move onto the next element.
        subsetsUtil(A, subset, i + 1,d)

        # exclude the A[i] from subset and
        # triggers backtracking.
        subset.pop(-1)
    return d
def subsetSums(arr, l, r,d, sum=0):
    if l > r:
        d.append(sum)
        return
    subsetSums(arr, l + 1, r,d, sum + arr[l])

    # Subset excluding arr[l]
    subsetSums(arr, l + 1, r,d, sum)
    return d
def print_factors(x):
    factors=[]
    for i in range(1, x + 1):
        if x % i == 0:
            factors.append(i)
    return(factors)
#-----------------------------------------------
def calc(X, d , ans,D):
    # print(X,d)
    if len(X) == 0:
        return

    i = X.index(max(X))
    ans[D[max(X)]] = d

    Y = X[:i]
    Z = X[i + 1:]

    calc(Y, d + 1,ans,D)
    calc(Z, d + 1,ans,D)

# endregion------------------------------
"""
def main():
    t = inpu()
    for _ in range(t):
        a,b,c = sep()
        l=[a,b,c]
        l.sort()
        if sum(l)%9==0 and l[0]>=sum(l)//9:
            print("YES")
        else:
            print("NO")
if __name__ == '__main__':
    main()

46417578 46590175 7599314
"""
"""
def main():
    t = inpu()
    for _ in range(t):
        s = inp()
        p=0
        cnt=len(s)
        q=0
        for i in range(cnt):
            if s[i] =="+":
                p+=1
            else:
                q+=1
            if q>p:
                cnt+=(i+1)
                q-=1
        print(cnt)
if __name__ == '__main__':
    main()
"""
"""
def main():
    t=inpu()
    for _ in range(t):
        n=inpu()
        i=1
        cnt=0
        i=1
        while(True):
            b = ((i*i)-1)/2
            if b>=n:
                break
            if b==int(b) and b>=1 and 1+b<=n:
                cnt+=1
            i+=2
        print(cnt)
if __name__ == '__main__':
    main()
"""
"""
def main():
    n = inpu()
    x=1
    while int(bin(x).replace("0b","")) <= n:
        x += 1
    print(x-1)
if __name__ == '__main__':
    main()
"""
"""
def main():
    a = [i for i, j in enumerate(input(), 1) if j == '1']
    m = int(input())
    q = [(-1, 0, 0, [])]
    p = 'NO'
    while q:
        x, y, z, t = q.pop()
        if z == m:
            p = 'YES\n' + ' '.join(map(str, t))
            break
        for i in a:
            if i != x and i > y:
                q.append((i, i - y, z + 1, t + [i]))
    print(p)
if __name__ == '__main__':
    main()
"""
"""
def main():
    t=inpu()
    for _ in range(t):
        n=inpu()
        arr=lis()
        i = k = 0
        while k < len(arr):
                k += 1
                j = arr.index(k)
                if j >= i:
                    arr.insert(i, arr.pop(j))
                    if i==j:
                        i=i+1
                    else:
                        i=j
        print(*arr)
if __name__ == '__main__':
    main()
"""
def main():
    for _ in range(int(input())):
        n = int(input())
        a = list(map(int, input().split()))
        k = []
        for i in a:
            x = int(math.log2(i))
            k.append(pow(2, x))
        print(*k)
if __name__ == '__main__':
    main()