给你一个数组 $$$x_2,x_3,\dots,x_n$$$。您的任务是找到任意数组 $$$a_1,\dots,a_n$$$,其中:
- $$$1\le a_i\le 10^9$$$ 对于所有 $$$1\le i\le n$$$。
- $$$x_i=a_i \bmod a_{i-1}$$$ 对于所有 $$$2\le i\le n$$$。
这里 $$$c\bmod d$$$ 表示整数 $$$c$$$ 除以整数 $$$d$$$ 的余数。例如$$$5 \bmod 2 = 1$$$、$$$72 \bmod 3 = 0$$$、$$$143 \bmod 14 = 3$$$。
注意,如果有多个 $$$a$$$ 满足该语句,则允许查找任何一个。
输入
第一行包含一个整数 $$$t$$$ $$$(1\le t\le 10^4)$$$ — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2\le n\le 500)$$$ - $$$a$$$ 中的元素数量。
每个测试用例的第二行包含 $$$n-1$$$ 整数 $$$x_2,\dots,x_n$$$ $$$(1\le x_i\le 500)$$$ — $$$x$$$ 的元素。
保证所有测试用例的 $$$n$$$ 值之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出任何满足语句的 $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) 。
示例
输入 #1
5 4 2 4 1 3 1 1 6 4 2 5 1 2 2 500 3 1 5
输出 #1
3 5 4 9 2 5 11 5 14 16 5 11 24 501 500 2 7 5
注意
在第一个测试用例中 $$$a=[3,5,4,9]$$$ 满足条件,因为:
- $$$a_2\bmod a_1=5\bmod 3=2=x_2$$$;
- $$$a_3\bmod a_2=4\bmod 5=4=x_3$$$;
- $$$a_4\bmod a_3=9\bmod 4=1=x_4$$$;