시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 65 29 26 50.000%

## 문제

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

## 예제 입력

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


## 예제 출력

17
6
206