フィボナッチ数列（★3 Edition）（★★★）

問題文

本問題の強化版としてフィボナッチ数列（★4 Edition）があります。

本問題の $N$ の値は、 $N = 2$ に固定されています。

正整数 $N, M$ と長さ $N$ の数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられます。
数列 $X$ を以下のように定義します。

• $1 \leqq i \leqq N$ ならば $X_i = A_i$
• $i \geqq N + 1$ ならば $X_i = X_{i - 1} + X_{i - 2} + \cdots + X_{i - N}$

$X_M$ を求めてください。制約により、答えが $2^{63}$ 未満であることが保証されています。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1 \leqq T \leqq 100$
• $\color{red}N = 2$
• $1 \leqq M \leqq 80$
• $0 \leqq A_i \leqq 100$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。 ここで、$\mathrm{case}_i (i = 1, 2, \cdots, T)$ は $i$ 番目のテストケースです。

各テストケースは以下の形式で与えられます。

出力

標準出力に $T$ 行出力してください。 $i$ 行目 $(i = 1, 2, \cdots, T)$ には $i$ 番目のテストケースについての答えを出力してください。

各テストケースについて、$X_M$ を出力してください。

サンプル

4
2 7
1 1
2 1
0 0
2 15
2 3
2 80
100 100

13
0
1597
2341672834846768500

この入力では、$4$ 個のテストケースが与えられています。$1, 2, 4$ 番目のテストケースについて、以下のことが言えます。

• $1$ 番目のテストケースについて、 数列 $X$ は $(1, 1, 2, 3, 5, 8, 13, \cdots)$ です。 $7$ 項目は $13$ です。

• $2$ 番目のテストケースについて、 数列 $X$ の各要素はすべて $0$ です。

• $4$ 番目のテストケースについて、$32$-bit 整数型の範囲を超える可能性があることに注意してください。