뒤집기 mex

$\mathrm{mex}$는 주어진 수열에 없는 $0$ 이상의 정수 중 가장 작은 값을 뜻하는 함수이다. 준서는 $\mathrm{mex}$를 좋아하는 시우를 위해 $N$장의 카드로 놀이를 만들었다.

규칙은 다음과 같다. $1$번 단계부터 $N$번 단계까지 차례로 진행한다.

• $i$번 단계에서 준서가 $i$번 카드를 테이블에 놓는다. 카드의 앞면과 뒷면에는 각각 $0$ 이상의 정수 $A_i$, $B_i$가 적혀 있다.
• 시우는 테이블에 놓인 $i$개의 카드를 뒤집는 $2^i$가지 경우 각각에 대해, 위를 향한 면의 수를 수열로 보고 $\mathrm{mex}$ 값을 계산한다. 그다음 가능한 $\mathrm{mex}$ 값의 가짓수를 말한다.
• 준서는 시우의 답을 확인한 뒤 $i+1$번 단계로 넘어간다.

시우를 도와, 각 단계에서 시우가 말해야 하는 답을 구하자.

첫 번째 줄에 카드의 개수 $N$가 주어진다. $(1 \le N \le 10^6)$

두 번째 줄부터 $N$개의 줄에 걸쳐 각 줄마다 순서대로 $i$번 카드의 정보를 의미하는 두 정수 $A_i$, $B_i$가 공백으로 구분되어 주어진다. $(0 \le A_i, B_i \le 10^6)$

$i$번째 줄에 시우가 $i$번 단계에서 말해야 하는 답을 출력한다.