#625 Dropping Monkeys

Statement

Statement language

A tower has floors numbered $1$ through $H$ from bottom to top. Initially, $a_i$ monkeys hang from floor $i$ .

Ishigami and Iino take turns removing one remaining floor. Ishigami moves first. When a floor is removed, all monkeys hanging from it move to the highest remaining floor below it. If no such floor exists, they fall to the ground, and the player who removed the floor scores one point for each monkey that falls.

The game continues until all floors have been removed. Each player acts to maximize their own final score. Find both players' final scores.

Input

The input is given in the following format:

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

Output

For each test case, print Ishigami's final score and Iino's final score, in that order, on one line.

Constraints

$1 \leq T \leq 1\,000\,000$ .
$1 \leq H \leq 1\,000\,000$ .

Subtasks

#	Score	Constraints
1	17	$H \leq 8$ , and the sum of $H$ over all test cases is at most $2\,000$ .
2	31	$H \leq 2\,000$ , and the sum of over all test cases is at most .

Samples

Input

Output

0
2
16

In the second case, Ishigami can remove floor $3$ , Iino can remove floor $1$ , and Ishigami can remove the last floor. Their scores are $11$ and $2$ .