Yuki keeps $n$ milk dragons at home. The $i$-th milk dragon has an attack power of $a_i$ and a defense power of $b_i$.

For the $i$-th milk dragon and the $j$-th milk dragon ($i \neq j$), if $a_i > b_j$, then the $i$-th milk dragon will attack the $j$-th milk dragon.

For each positive integer $k \le n$, you need to find the maximum number of milk dragons that can be selected from the first $k$ milk dragons such that no selected milk dragon attacks another selected milk dragon.

Input

• The first line contains a positive integer $c$, representing the test case number. The sample satisfies $c=0$.
• The second line contains a positive integer $n$.
• The next $n$ lines each contain two positive integers $a_i, b_i$. It is guaranteed that all $a_i, b_i$ are distinct.

Output

Output $n$ lines, where the $i$-th line contains an integer representing the answer for $k=i$.

Examples

Input 1

0
3
1 6
3 2
5 4

Output 1

1
2
2

Note 1

• For $k=1$, it is obvious that only the first milk dragon can be selected.
• For $k=2$, the first two milk dragons can be selected.
• For $k=3$, if all milk dragons are selected, the third milk dragon will attack the second milk dragon. Therefore, the maximum answer is $2$.

Input 2

See loong/loong2.in and loong/loong2.ans.

Output 2

See loong/loong2.in and loong/loong2.ans.

Input 3

See loong/loong3.in and loong/loong3.ans.

Output 3

See loong/loong3.in and loong/loong3.ans.

Input 4

See loong/loong4.in and loong/loong4.ans.

Output 4

See loong/loong4.in and loong/loong4.ans.

Input 5

See loong/loong5.in and loong/loong5.ans.

Output 5

See loong/loong5.in and loong/loong5.ans.

Input 6

See loong/loong6.in and loong/loong6.ans.

Output 6

See loong/loong6.in and loong/loong6.ans.

Input 7

See loong/loong7.in and loong/loong7.ans.

Output 7

See loong/loong7.in and loong/loong7.ans.

Constraints

For all test data, it is guaranteed that:

• $1 \le n \le 10^6$;
• $1 \le a_i, b_i \le 2n$, and all $a_i, b_i$ are distinct.

• Special Property A: Guaranteed $a_i > b_i$.
• Special Property B: Guaranteed $a_i < b_i$.
• Special Property C: Guaranteed that no more than $100$ milk dragons satisfy $a_i > b_i$.