Phù thủy đếm bit

Phù thủy Merlin đang huấn luyện phép thuật bit với học trò. Anh ta bắt đầu với một con số ma thuật \(a = 0\) và thực hiện \(q\) phép biến đổi thuộc một trong các loại sau:

• Phép XOR ma thuật: "1 \(x\)" - Biến đổi \(a\) thành \(a \oplus x\) (phép XOR với \(x\))
• Phép triệt tiêu bit quyền lực: "2" - Tắt bit mạnh nhất (MSB) của \(a\). Nếu \(a = 0\), bỏ qua phép thuật này
• Phép đếm năng lượng: "3" - Đếm số bit bật (số lượng năng lượng) trong \(a\)

Bit mạnh nhất (MSB): Là bit bật nằm tận cùng bên trái. Ví dụ với số \(36\) (nhị phân: \(100100_2\)), MSB là bit thứ 5, sau khi tắt được \(4\) (\(100_2\))

Input

• Dòng đầu tiên gồm một số nguyên \(q\).
• \(q\) dòng tiếp theo, mỗi dòng gồm một truy vấn theo định dạng trên.

Output

• In ra đáp án là một số nguyên cho mỗi truy vấn loại \(3\).

Example

5
2
1 5
3
2
3

2
1