시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB113554654.762%

## 문제

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:

$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|}$$.

## 예제 입력 1

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


## 예제 출력 1

17
6
206