#362 Tile Covering

Statement

Statement language

jkrt wants to cover a board of length $N$ exactly with tiles.

Choose two distinct positive integers $A$ and $B$ , and place tiles of lengths $A$ and $B$ alternately. Both the first and the last tile must have length $A$ , and each of the two tile lengths must be used at least once.

Find the number of ordered pairs $(A,B)$ for which the board can be covered exactly without overlaps or extending beyond the board.

Input

The input is given from Standard Input in the following format:

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

Output

For each test case, print the number of valid ordered pairs $(A,B)$ on one line.

Constraints

$1 \leq T \leq 20$ .
$4 \leq N \leq 10^{10}$ .

Subtasks

#	Score	Constraints
1	22	$N \leq 10^3$ .
2	31	$N \leq 10^6$ .

Samples

Input

Output

For $N=4$ , the only valid ordered pair is $(1,2)$ . Tiles of lengths $1,2,1$ cover the board exactly.