1. The first line represents - a polynomial in of degree with non-negative integer coefficients in increasing order of the power:
   
   where , . This polynomial is codified by its degree followed by the coefficients , . All the numbers are separated by a single space.
2. The second line is the positive integer .
3. The third line is the positive integer .

It is assumed that the polynomial is a polynomial of degree less or equal than 20 ( ) with non-negative integer coefficients less or equal than 10000 ( , ); ; .

Output

The output is a sequence of lines, one for each test case. Each of these lines contains the th integer in the sequence  for the corresponding test case. This value is less or equal than .

Sample Input

2
4 3 0 0 0 23
25
100
1 0 1
1
6

Sample Output

1866
3

#include <stdio.h>
long long mypow(long long x, long long y) {
    if(y == 0)  return 1;
    if(y&1)
        return x*mypow(x*x, y/2);
    else
        return mypow(x*x, y/2);
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n, d, k, i, j;
        scanf("%d", &n);
        long long c[30];
        for(i = 0; i <= n; i++)
            scanf("%lld", &c[i]);
        scanf("%d %d", &d, &k);
        int tk = 0, tb = 0;
        for(i = 1; ; i++) {
            long long an = 0;
            for(j = 0; j <= n; j++)
                an += c[j]*mypow(i, j);
            tb += d;
            tk += tb;
            if(tk >= k) {
                printf("%lld\n", an);
                break;
            }
        }
    }
    return 0;
}