다항식

계수가 모두 정수인 차수 $t$의 다항식 $f(k)$가 다음과 같이 주어진다.

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

음이 아닌 정수 $n$에 대해 $f(0), f(1), \dots, f(n)$의 합을 $S(n)$이라 하자.

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

$S(n)$도 다항식이다. 다만 차수가 $t+1$이고 계수는 유리수이므로 다음과 같이 쓸 수 있다.

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

여기서 각 $i = 0, 1, \dots, t+1$에 대해 $a_i$와 $b_i$는 서로소인 정수다. 즉 1보다 큰 공약수가 없다. 계수가 0인 자리는 $a_i = 0$, $b_i = 1$로 정해진다.

정수 계수 $c_0, \dots, c_t$로 주어진 차수 $t$의 다항식 $f(k)$에 대해 $S(n)$을 구하고, 다음 값을 출력하는 프로그램을 작성하라.

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

다항식에 대한 다음 항등식을 활용해도 된다. 임의의 양의 정수 $d$와 임의의 실수 $x$에 대해

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

이고, $0 \le i \le d$인 정수 $i$에 대해 $\binom{d}{i} = \frac{d!}{i!(d-i)!}$이다.

입력은 표준 입력으로 읽는다. 입력은 $T$개의 테스트 케이스로 이루어지고, 첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 한 줄이다. 그 줄에는 음이 아닌 정수 $t$ ($0 \le t \le 25$)가 먼저 오고, 이어서 정수 $c_0, \dots, c_t$가 $t+1$개 온다. $-10 \le c_0, \dots, c_t \le 10$이고 $c_t \ne 0$이다. 이 값이 차수 $t$이고 계수가 $c_0, \dots, c_t$인 다항식 $f(k) = c_0 + c_1k + c_2k^2 + \cdots + c_tk^t$를 완전히 결정한다.

출력은 표준 출력으로 쓴다. 테스트 케이스마다 정확히 한 줄을 출력한다. 그 줄에는 값 $\sum_{i=0}^{t+1}{\left| a_i \right|}$를 나타내는 정수 하나를 적는다.