Polynomial

A polynomial $f(k)$ of degree $t$ whose coefficients are all integers is given as

$f(k) = c_0 + c_1k + c_2k^2 + \cdots + c_tk^t$

For a nonnegative integer $n$, let $S(n)$ be the sum of $f(0), f(1), \dots, f(n)$.

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

$S(n)$ is a polynomial as well. Its degree is $t+1$ and its coefficients are rational, so it can be written as

$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 for each $i = 0, 1, \dots, t+1$ the integers $a_i$ and $b_i$ are relatively prime, that is, they have no common divisor greater than 1. A coefficient that equals zero is written with $a_i = 0$ and $b_i = 1$.

Given a polynomial $f(k)$ of degree $t$ with integer coefficients $c_0, \dots, c_t$, write a program that computes $S(n)$ and prints the value

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

You may use the following 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 reads from standard input. The input consists of $T$ test cases, and the number of test cases $T$ is given on the first line.

Each test case is a single line. The line starts with a nonnegative integer $t$ ($0 \le t \le 25$), followed by $t+1$ integers $c_0, \dots, c_t$ with $-10 \le c_0, \dots, c_t \le 10$ and $c_t \ne 0$. These values fully describe the 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 writes to standard output. Print exactly one line for each test case. The line contains one integer, the value $\sum_{i=0}^{t+1}{\left| a_i \right|}$.