Kapti and Balu are friends. Kapti is very good in math and is always saying that no one can challenge him in math. One day Balu decided to check Kapti that he is really good in math or he is just making fool.

Balu gave Kapti a polynomial of degree “n” and ask Kapti to find constant term “L” if the polynomial was first expressed in Factorial Notation and then subjected to Forward Difference operator for “k” imes.

If

      f(x) = a1xn + a2xn-1 + ... + anx + l

then its factorial notation will be:

      fFN(x) = A1[x]n + A2[x]n-1 + ... + An[x] + L

Where

      [x]n = x(x-1)(x-2) ... (x-n+1)

And forward difference operator Δ is just simple differentiation of f_FN(x).

For example

      f(x) = 2x3 - 3x2 + 3x - 10
      fFN(x) = 2[x]3 + 3[x]2 + 2[x] - 10
      ΔfFN(x) = 6[x]2 + 6[x] + 2 here constant term L = 2 and k = 1;

Help kapti in proving himself that he is good in math.

Input

Input start with integer T (< 30) denoting the number of test cases.

Each test case will contains two lines,

First line contains n (<= 25) and k (<= n)

Second line contains n+1 integers a₁ a₂ a₃ ... a_n l, -50 <= a_i <= 50

Output

For each test case print one line containing L.

Example

Input:
1
3 2
2 -3 3 -10

Output:
6