Flippy MEX

$\mathrm{mex}$ is the function that returns the smallest non-negative integer missing from a given sequence. Junseo made a game with $N$ cards for Siwoo, who likes $\mathrm{mex}$.

The rules are as follows. The steps run from $1$ to $N$ in order.

• In step $i$, Junseo places card $i$ on the table. The front and back of the card have non-negative integers $A_i$ and $B_i$ written on them.
• For each of the $2^i$ ways to flip the $i$ cards on the table, Siwoo treats the numbers facing up as a sequence and computes its $\mathrm{mex}$. Then Siwoo states how many distinct $\mathrm{mex}$ values are possible.
• Junseo checks Siwoo's answer and moves on to step $i+1$.

Help Siwoo find the answer Siwoo should state at each step.

The first line contains the number of cards $N$. $(1 \le N \le 10^6)$

From the second line onward, each of the next $N$ lines contains two integers $A_i$ and $B_i$, separated by a space, which give the information for the $i$-th card. $(0 \le A_i, B_i \le 10^6)$

On the $i$-th line, print the answer Siwoo should state in step $i$.