#607 Deadly Assassins

Loading problem...

Preparing the statement, recent submissions, and submit form.

Authors: jakekim

Time limit: 3000 ms
Python time limit: 15000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

Statement language

You process queries in order. In query $i$ , hire a new assassin numbered $i$ and choose an integer $a_i$ . If $a_i=0$ , assassin $i$ targets nobody. Otherwise, assassin $i$ targets the previously hired assassin $a_i$ .

After each query, assassin $x$ is dead if at least one living assassin targets $x$ . Otherwise, $x$ is alive. Thus, when an assassin who targets someone dies, their target may become alive again.

Find the number of living assassins after each query.

Input

The input is given in the following format:

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

Output

For each case, print the number of living assassins after each query, one per line.

Constraints

$1\leq T\leq100\,000$ .
$1\leq N\leq100\,000$ .
$0 \leq_{}$ .

Subtasks

#	Score	Constraints
1	20	$N\leq200$ . The sum of $N^2$ over all cases is at most $40\,000$ .
2	80	No additional constraints.

Samples

Input

Output

Editorial

View editorial

a

i

<

i

0\leq a_i<i