暂无测试数据。

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