Charles Babbage's Difference Engine

A difference engine is an automatic mechanical calculator that tabulates the values of a polynomial. Its name comes from the method of divided differences, which interpolates or tabulates a function from a small set of polynomial coefficients. Logarithmic and trigonometric functions, both used constantly by navigators and scientists, can be approximated by polynomials, so one difference engine can compute many useful sets of numbers.

Teams of mathematicians and the human clerks known as computers kept letting errors into printed tables. That difficulty pushed Charles Babbage to automate the work with a machine.

The engine runs on Newton's method of divided differences, also called the method of finite differences. Once the value of a polynomial and of its finite differences is known at one value of $x$, the engine can calculate any number of nearby values. Take the quadratic $p(x) = 2x^2 - 3x + 2$ and the goal of tabulating $p(0), p(1), p(2), p(3), p(4)$ and onward. In the table below the second column holds the values of the polynomial, the third column holds the difference of the two neighboring entries in the second column, and the fourth column holds the difference of the two neighboring entries in the third column.

The numbers in the third value column are constant. Starting from any polynomial of degree $n$, value column number $n + 1$ is always constant, and the whole method rests on that fact.

The first entry of each column comes from $n + 1$ consecutive values of the function. Compute those values, then work backwards and take the differences you need.

Write a program that reproduces Babbage's difference engine. Given $p(0)$ through $p(n)$ for a polynomial of degree at most $n$, run the table forward to $x = 50$ and report $p(50)$.

The first line contains a single positive integer $T$, the number of test cases ($1 \le T \le 1000$).

Each of the next $T$ lines holds one test case in the form

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

where $n$ is the degree of the polynomial with $0 \le n < 6$, followed by the $n + 1$ integers $p(0)$ through $p(n)$. Every value satisfies $|p(i)| \le 10^9$.

For each test case print one line of the form Case #x: M, where x is the case number starting from 1 and M is $p(50)$ for that polynomial. The answer fits in a signed 64-bit integer.