#581 Rating Updates

Statement

Statement language

The initial rating is $R_0$ . You participate in $N$ contests in order, and your performance in the $i$ -th contest is $P_i$ .

After each contest, the rating is updated by giving weight $3$ to the previous rating and weight $1$ to the current performance. The rating $R_i$ after the $i$ -th contest is

R_i=\frac{3R_{i-1}+P_i}{4}.

It is guaranteed that $R_i$ is a positive integer for every $i$ ( $1\leq i\leq N$ ).

Find the final rating $R_N$ .

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the final rating $R_N$ on one line.

Constraints

$1 \leq T \leq 100\,000$ .
$1 \leq N \leq 200\,000$ .
$1 \leq_{}$ .

Subtasks

#	Score	Constraints
1	37	$P_i\geq R_{i-1}$ ( $1 \leq i \leq$ ).

Samples

Sample 1

Input

Output

110
2
4

In the first case, the rating changes as $100 \longrightarrow 105 \longrightarrow 100 \longrightarrow 110$ .

Sample 2

Input

2
2 500000000
500000000 500000000
2 100
60 54

Output

500000000
81

In the first case, each performance equals the current rating, so the rating stays unchanged. In the second case, it changes as $100 \longrightarrow90 \longrightarrow81$ .