Sam and Dean fight the supernatural creatures to protect the humans. Now they have come across a creature called the Vedala, which are always found in pairs. Each Vedala can be represented by a polynomial. Both the Vedalas need to be killed at once or else they can't be killed. They can be killed only by using the product of the two polynomials representing the two Vedala. Help Sam and Dean find the product of the polynomials fast, so they can do their work. 

Input

First line contains an integer T (≤ 10), number of test cases.

Each test case will have n (n ≤ 10000), maximum degree of the polynomials on the first line. 

Next two lines will have n+1 space separated integers each representing the coefficients of first and second polynomials respectively.

All input coefficients values are ≤ 1000.

Output

For each test case output a line of 2n space separated integers indicating coefficients of the polynomial created after multiplication.

Example

Input:
2
2
1 2 3
3 2 1
2
1 0 1
2 1 0

Output:
3 8 14 8 3
2 1 2 1 0

Explanation

1st test case n=2, the polynomials are x² + 2x + 3 and 3x² + 2x + 1.

On multiplying we get 3x⁴ + 8x³ + 14x² + 8x + 3 and hence the answer is 3 8 14 8 3.

2nd test case n=2, the polynomials are x² + 1 and 2x² + x. 

On multiplying we get 2x⁴ + x³ + 2x² + x and hence the answer is 2 1 2 1 0.