We consider a sequence $A$ with $p$ float-point numbers denoted by $a_0, a_1, ..., a_{p-1}$ where $p$ is a prime number. To simplify our problem, we guarantee that $p$ must be $13$, $103$ or $100003$.

To make a decomposition for this sequence, we define the kernal functions $r(h,k) = 2^{sin^3\big(2\pi\frac{hk}{p}\big)}$. Therefore we can get the new sequence $B = \{b_0,b_1,\cdots,b_{p-1}\}$ tranformed from the original sequence $A$ where $b_k = \sum_h a_h * r(h,k)$.

Your mission is to calculate the new sequence $B$.

Input

The first line is the number of test cases. Each test case contains two lines. The first line contains an integer $p$. The second line contains $p$ float-point numbers corresponding to the sequence $A$.

Output

For each test case, output $p$ float-point numbers rounded to three decimal places in one line corresponding to the sequence $B$.

Example

Input

13
7 0 0 0 0 0 0 0 0 0 0 0 0
13
1 2 3 4 5 6 7 8 9 10 11 12 13
13
11 7 7 7 7 7 7 7 7 7 7 7 7

Output

7.000 7.000 7.000 7.000 7.000 7.000 7.000 7.000 7.000 7.000 7.000 7.000 7.000
91.000 85.477 92.015 93.543 91.049 99.763 98.551 98.517 97.304 106.018 103.525 105.053 111.590
95.000 102.032 102.032 102.032 102.032 102.032 102.032 102.032 102.032 102.032 102.032 102.032 102.032