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

</p>

0 1

1 1

1 2 3

31 41 59 26

---------------------------------------------------------------

Explanation for the 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

Explanation for the 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)=x2

h(x)=g(x)/x so h(x)=x=0+1x

output : 0 1

Explanation for the 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+x2

h(x)=g(x)/x so h(x)=1+1x

output : 1 1

---------------------------------------------------------------

 

See also: Another problem added by Tjandra Satria Gunawan