Cho một tập hợp rỗng, bạn sẽ lần lượt thực hiện N thao tác. Có hai loại thao tác:

• Thao tác 1: (1, x) – thêm số x vào tập hợp.
• Thao tác 2: (2, x) – loại bỏ một số x ra khỏi tập hợp (dữ liệu đảm bảo trước đó có ít nhất một số x).

Sau mỗi thao tác, hãy in ra ước chung lớn nhất (gcd) của các số đang có trong tập hợp. Nếu tập hợp rỗng, in ra 1.

Input

• Dòng đầu tiên: số tự nhiên N (1 ≤ N ≤ 1000).
• N dòng tiếp theo, mỗi dòng gồm hai số t (loại thao tác) và x (số cần xử lý) với 1 ≤ t ≤ 2, 1 ≤ x ≤ 109.

Output

• Gồm N dòng, mỗi dòng là gcd của tập hợp sau thao tác tương ứng (nếu rỗng in 1).

Example

6
1 8
1 12
1 10
1 8
2 8
2 8

8
4
2
2
2
2