Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

C. Assembly via Remainders
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array x2,x3,,xn. Your task is to find any array a1,,an, where:

  • 1ai109 for all 1in.
  • xi=aimod for all 2\le i\le n.

Here c\bmod d denotes the remainder of the division of the integer c by the integer d. For example 5 \bmod 2 = 1, 72 \bmod 3 = 0, 143 \bmod 14 = 3.

Note that if there is more than one a which satisfies the statement, you are allowed to find any.

Input

The first line contains a single integer t (1\le t\le 10^4) — the number of test cases.

The first line of each test case contains a single integer n (2\le n\le 500) — the number of elements in a.

The second line of each test case contains n-1 integers x_2,\dots,x_n (1\le x_i\le 500) — the elements of x.

It is guaranteed that the sum of values n over all test cases does not exceed 2 \cdot 10^5.

Output

For each test case output any a_1,\dots,a_n (1 \le a_i \le 10^9) which satisfies the statement.

Example
Input
5
4
2 4 1
3
1 1
6
4 2 5 1 2
2
500
3
1 5
Output
3 5 4 9
2 5 11
5 14 16 5 11 24
501 500
2 7 5
Note

In the first test case a=[3,5,4,9] satisfies the conditions, because:

  • 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;