我们考虑一个包含 $p$ 个浮点数的序列 $A$，记为 $a_0, a_1, ..., a_{p-1}$，其中 $p$ 是一个质数。

为了简化问题，我们保证 $p$ 必须为 $13$、$103$ 或 $100003$。

为了对该序列进行分解，我们定义核函数 $r(h,k) = 2^{sin^3\big(2\pi\frac{hk}{p}\big)}$。

因此，我们可以得到由原始序列 $A$ 变换而来的新序列 $B = \{b_0,b_1,\cdots,b_{p-1}\}$，其中 $b_k = \sum_h a_h * r(h,k)$。

你的任务是计算出新的序列 $B$。

输入格式

第一行是测试用例的数量。每个测试用例包含两行。第一行包含一个整数 $p$。第二行包含 $p$ 个浮点数，对应序列 $A$。

输出格式

对于每个测试用例，在单行中输出 $p$ 个保留三位小数的浮点数，对应序列 $B$。

样例

输入样例 1

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

输出样例 1

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