暂无测试数据。

Background

有一天，你得到了两个数列$a_n$和$b_n$。你突发奇想：如果给出一个$k$，那么$a_i\times b_{i-k}$的值是什么呢？于是你决定去问小$A$。由于你问的实在是太多了，小$A$ 很烦，于是就问到你要这些值干什么。原来你要找出其中$n$项求和，当作一个$key$。于是，小$A$提前算出来了所有的和。但你有些不放心：他算得对吗？于是你要检验一下。

Description

给定数列$a_n, b_n$，对于不同的$k\in[0,n]$求
$$\sum_{i=k}^n a_i\times b_{i-k}$$

Format

Input

输入包含多组数据
输入的第一行为一个整数$T$，表示有$T$组数据
每组数据的第一行为一个整数$n$，接下来有$n$行，表示$a_i, b_i$

Output

对于第$j$组数据，你应该输出$n_j$行，对于第$i$行，表示当$k=i-1$时，原和式的值。

Sample 1

Input

2
4
2 5
3 3
4 4
9 7
5
113 266
955 358
128 249
584 722
117 233

Output

98
63
47
45
852729
529744
272253
197230
31122

Limitation

对于所有测试点，分配512MB内存和2.0s时间。对于$\sum nT$较大的测试点，提供2.0 ~ 15.0s时间

对于60%的测试点，有$T = 1, 0 < n < 10^5$
对于所有的测试点，有$T < 10, 0 < n < 10^6$

对于50%的测试点，有$a_i , b_i < 10^3$
对于所有的测试点，有$a_i , b_i < 10^{100,000}$
对于所有的测试点，有$a_i, b_i \in \mathbb N$

Source

Original