A polynomial (f(k)) of degree (t) with integral coefficients is given as (f(k) = c_0 + c_1k + c_2k^2 + \cdots + c_tk^t), where the coefficients (c_0, \dots, c_t) are all integers. Here, we are interested in the sum (S(n)) of (f(0)), (f(1)), ..., and (f(n)) for any nonnegative integer (n). That is, (S(n)) is defined by:</p>

[S(n) = \sum_{k=0}^{n}{f(k)} = f(0) + f(1) + \cdots + f(n)]

The sum (S(n)) is a polynomial, too, but is of degree (t + 1) and rational coefficients. It can thus be represented by:

[S(n) = \frac{a_0}{b_0} + \frac{a_1}{b_1}n + \frac{a_2}{b_2}n^2 + \cdots + \frac{a_{t+1}}{b_{t+1}}n^{t+1}]

where (a_i) and (b_i) are integers that are relatively prime for each (i = 0, 1, \dots, t+1) or equivalently, that have no common divisor greater than 1.

Given a polynomial (f(k)) of degree (t) with integeral coeffcients (c_0, \dots, c_t), your program is to compute (S(n)) for the given polynomial (f(k)) and to output the following value

[\sum_{i=0}^{t+1}{\left| a_i \right| }]

where the (a_i) are determined as above for such a representation of (S(n) = \frac{a_0}{b_0} + \frac{a_1}{b_1}n + \frac{a_2}{b_2}n^2 + \cdots + \frac{a_{t+1}}{b_{t+1}}n^{t+1}).

You may exploit the following known identity for polynomials: for any positive integer (d) and any real (x),

[(x+1)^d - x^d = 1 + \binom{d}{1}x + \binom{d}{2}x^2 + \dots + \binom{d}{d-1}x^{d-1}]

where (\binom{d}{i} = \frac{d!}{i!(d-i)!}) for any integer (i) with (0 \le i \le d).

입력 형식

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of only a single line containing a nonnegative integer (t) ((0 \le t \le 25)) and (t+1) following integers (c_0, \dots, c_t) with (-10 \le c_0, \dots, c_t \le 10) and (c_t \ne 0). This fully describes the input polynomial (f(k) = c_0 + c_1k + c_2k^2 + \cdots + c_tk^t) of degree (t) with coefficients (c_0, \dots, c_t).

출력 형식

Your program is to write to standard output. Print exactly one line for each test case. The line should contain an integer representing the value (\sum_{i=0}^{t+1}{\left| a_i \right|}).

예제 입력

3
3 1 1 1 1
5 0 -1 0 1 0 -1
5 -3 10 9 2 -7 5

예제 출력

17
6
206