Ngoài Mạnh SadBoy, trong câu lạc bộ lập trình* Programming Lab* của IUH còn có một thành viên đặc biệt khác anh ấy tên là BanQ. BanQ là một người năng động và hài hước, anh ấy có đam mê đặc biệt với toán học và lập trình. Do là một con người hướng ngoại nên năm mới này BanQ được rất nhiều lì xì từ cô chú trong gia đình thế nhưng không phải với bao lì xì nào BanQ cũng cảm thấy hạnh phúc.

Trong các bao lì xì của BanQ, mỗi bao sẽ chứa ~x~ tiền (~1 \leq x \leq 10^6~). Chỉ số hạnh phúc của BanQ là số lượng cặp nguyên tố cùng nhau của các giá trị tiền trong các bao lì xì mà BanQ có.

Cụ thể, BanQ sẽ có ~q~ thao tác tác động đến số lượng bao lì xì của mình trong năm mới. Với mỗi thao tác sẽ thuộc ~1~ trong ~2~ loại sau:

• Loại ~1~: BanQ nhận được một bao lì xì có giá trị là ~x~ tiền (~1 \leq x \leq 10^6~).
• Loại ~2~: BanQ sẽ lấy ra một bao lì xì có giá trị là ~x~ tiền (~1 \leq x \leq 10^6~) để lì xì cho các em nhỏ.

Với mỗi thao tác, bạn hãy cho biết chỉ số hạnh phúc của BanQ hiện tại là bao nhiêu.

Input

Dòng đầu tiên chứa số nguyên ~q~ (~1 \leq q \leq 10^5~) là số lượng thao tác tác động đến số lượng bao lì xì của BanQ.

~q~ dòng tiếp theo mỗi dòng sẽ chứa ~2~ số nguyên ~t~ và ~x~ (~1 \leq t \leq 2, 1 \leq x \leq 10^6~) là loại thao tác và số tiền của bao lì xì tương ứng.

Đảm bảo với thao tác loại ~2~ BanQ vẫn đang có bao lì xì tương ứng.

Output

Với mỗi thao tác, bạn hãy in ra màn hình chỉ số hạnh phúc hiện tại của BanQ.

Sample Input

6
1 11
1 31
2 11
1 2024
1 1902
2 31

Sample Output

0
1
0
1
2
0

SubTask

• SubTask 1: ~ 30\% ~ số test, với ~q \leq 10^3~.
• SubTask 2: ~70\%~ số test còn lại, không có ràng buộc gì thêm.