찰스 배비지의 차분기관

차분기관은 다항식의 값을 표로 만들어 주는 기계식 자동 계산기다. 이름은 분할 차분법에서 왔다. 분할 차분법은 다항식 계수 몇 개만으로 함수를 보간하거나 표로 만드는 방법이다. 항해사와 과학자가 늘 쓰는 로그 함수와 삼각 함수도 다항식으로 근사할 수 있어서, 차분기관 하나로 유용한 수표를 여러 종류 계산할 수 있다.

수학자와 컴퓨터라 불린 계산원이 손으로 만든 수표에는 오류가 끊이지 않았다. 찰스 배비지는 이 작업을 기계로 자동화하려 했다.

차분기관의 원리는 뉴턴의 분할 차분법이고, 유한 차분법이라고도 부른다. 어떤 $x$에서 다항식의 값과 그 유한 차분을 한 번 구해 두면, 기관은 그 근처의 값을 얼마든지 계산할 수 있다. 이차 다항식 $p(x) = 2x^2 - 3x + 2$의 $p(0), p(1), p(2), p(3), p(4)$를 차례로 표로 만드는 경우를 보자. 아래 표에서 둘째 열은 다항식의 값이고, 셋째 열은 둘째 열에서 이웃한 두 값의 차이고, 넷째 열은 셋째 열에서 이웃한 두 값의 차다.

셋째 값 열의 수는 일정하다. 차수가 $n$인 다항식에서 출발하면 값 열의 $n + 1$번째는 항상 일정하고, 이 방법 전체가 그 사실에 기댄다.

각 열의 첫 값은 함수의 연속한 값 $n + 1$개에서 얻는다. 그 값을 먼저 구하고, 거꾸로 필요한 차를 계산하면 된다.

배비지의 차분기관을 재현하는 프로그램을 작성하라. 차수가 $n$ 이하인 다항식의 $p(0)$부터 $p(n)$까지가 주어지면, 표를 $x = 50$까지 밀고 나가 $p(50)$을 구한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 1000$).

다음 $T$개 줄에 각각 테스트 케이스가 다음 형식으로 주어진다.

n p(0) p(1) p(2) ... p(n)

$n$은 다항식의 차수이고 $0 \le n < 6$이다. 그 뒤에 정수 $p(0)$부터 $p(n)$까지 $n + 1$개가 이어진다. 모든 값은 $|p(i)| \le 10^9$을 만족한다.

각 테스트 케이스마다 Case #x: M 형식으로 한 줄을 출력한다. x는 1부터 시작하는 케이스 번호이고, M은 그 다항식의 $p(50)$이다. 답은 부호 있는 64비트 정수 범위에 들어간다.