给定一个数组 $$$[a_1, a_2, \dots, a_n]$$$,使得 $$$1 \le a_i \le 10^9$$$。令$$$S$$$ 为数组$$$a$$$ 中所有元素的总和。
如果满足以下条件,我们称 $$$n$$$ 整数的数组 $$$b$$$ 为漂亮:
- $$$1 \le b_i \le 10^9$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$;
- 对于数组$$$(b_i, b_{i + 1})$$$中的每对相邻整数,要么$$$b_i$$$除$$$b_{i + 1}$$$,要么$$$b_{i + 1}$$$除$$$b_i$$$(或两者);
- $$$2 \sum \limits_{i = 1}^{n} |a_i - b_i| \le S$$$。
你的任务是找到任何漂亮的数组。可以证明,至少有一个美丽的数组总是存在的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
输出
对于每个测试用例,在单独的行上打印漂亮的数组 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$)。可以证明,在这种情况下,至少存在一种美丽的阵法。如果有多个答案,请打印其中任何一个。
示例
输入 #1
4 5 1 2 3 4 5 2 4 6 2 1 1000000000 6 3 4 8 1 2 3
输出 #1
3 3 3 3 3 3 6 1 1000000000 4 4 8 1 3 3