Tập ~S~ gồm các số nguyên dương. Ban đầu tập ~S~ rỗng.

Cho ~q~ thao tác thuộc một trong hai loại:

• Loại ~1~: Thêm số nguyên dương ~x~ vào tập ~S~
• Loại ~2~: Xoá số nguyên dương ~x~ khỏi tập ~S~ (nếu tập ~S~ chứa nhiều số có giá trị bằng ~x~ thì chỉ xóa một số)

Sau mỗi thao tác, in ra số cặp số nguyên tố cùng nhau thuộc tập ~S~. Hai số được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng ~1~.

Input

• Dòng đầu tiên gồm số thao tác ~q~ ~(1 \le q \le 10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~t~ và ~x~ lần lượt là loại thao tác và số nguyên dương ~x~ cần thêm vào hoặc xoá khỏi tập ~S~ ~(1 \le t \le 2, 1 \le x \le 10^6)~.
• Dữ liệu đảm bảo với mỗi thao tác loại ~2~ luôn tồn tại số nguyên dương ~x~ trong tập ~S~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là số cặp số nguyên tố cùng nhau thuộc tập ~S~ sau thao tác thứ ~i~.

Samples

Sample Input 1

3
1 1
1 2
1 3

Sample Output 1

0
1
3

Sample Input 2

5
1 2
1 5
1 3
1 10
2 3

Sample Output 2

0
1
3
4
1

Scoring

• Subtask ~1~ (~30\%~ số test): ~q \le 10^3~
• Subtask ~2~ (~70\%~ số test): Không có ràng buộc gì thêm