#362 Tile Covering

Loading problem...

Preparing the statement, recent submissions, and submit form.

#362 Tile Covering

DOJ/Beginner Contest DOJ/BCD 7

Authors: 2

Time limit: 2000 ms
Python time limit: 6000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

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$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$

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$ .
3	47	No additional constraints.

Samples

Input

Output

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

Editorial

View editorial