Given polynomial of degree d, f(x) = c₀ + c₁x + c₂x² + c₃x³ + ... + c_dx^d

For each polynomial f(x) there exists polynomial g(x) such that:

• f(x) = g(x) - g(x - 1) for each integer x
• g(0) = 0

Your task is to calculate polynomial h(x) = g(x) / x.

(Note : degree of polynomial h(x) = degree of polynomial f(x))

Input

The first line of input contain an integer T, T is number of test cases (0 < T ≤ 10⁴)

Each test case consist of 2 lines:

• First line of the test case contain an integer d, d is degree of polynomial f(x) (0 ≤ d ≤ 18)
• Next line contains d+1 integers c₀, c₁ ... c_d, separated by space, represent the coefficient of polynomial f(x) (-2³¹ < c₀, c₁ ... c_d < 2³¹ and c_d ≠ 0)

Output

For each test case, output the coefficient of polynomial h(x) separated by space. Each coefficient of polynomial h(x) is guaranteed to be an integer.

Example

Input:
5
0
13
1
-1 2
1
0 2
2
2 -5 9
3
23 9 21 104

Output:
13
0 1
1 1
1 2 3
31 41 59 26

Explanation

First Test Case

• f(x) = 13
• g(x) that satisfy: g(x) - g(x - 1) = f(x) = 13 and g(0) = 0 is: g(x) = 13x
• h(x) = g(x)/x so h(x) = 13
• output : 13

Second Test Case

• f(x) = -1 + 2x
• g(x) that satisfy: g(x) - g(x - 1) = f(x) = -1 + 2x and g(0) = 0 is: g(x) = x²
• h(x) = g(x) / x so h(x) = x = 0 + 1x
• output : 0 1

Third Test Case

• f(x) = 0 + 2x
• g(x) that satisfy: g(x) - g(x - 1) = f(x) = 2x and g(0) = 0 is: g(x) = x + x²
• h(x) = g(x) / x so h(x) = 1 + 1x
• output : 1 1

See also: Another problem added by Tjandra Satria Gunawan