問題文

非負整数 $a, b, c$ が与えられます。この $3$ つの数に対し、以下の操作を $K$ 回行います。

• $a, b, c$ をそれぞれ $\lfloor \frac{b + c}{2} \rfloor, \lfloor \frac{c + a}{2} \rfloor, \lfloor \frac{a + b}{2} \rfloor$ へ同時に置き換える。

$K$ 回操作を行った後の $a + b + c$ の値を求めてください。

$1$ つの入力につき $T$ 個のテストケースについて解いてください。

入力

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

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

$a$ $b$ $c$ $K$

• 入力はすべて整数
• $1\leq T\leq 10^5$
• $0\leq a, b, c, K \leq 10^{18}$

出力

$T$ 行出力してください。$i$ 行目（$1\leq i\leq T$）には、$\mathrm{case}_i$ の答えを出力してください。

サンプル

3
10 6 3 2
0 1 1 10
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

18
0
3000000000000000000