Sinan and Fahri are playing an XOR game. Initially, Sinan has an empty set of integers. Then a sequence of \(\mathbf{N}\) events happens. There are two types of events:

• Sinan chooses integer \(\mathbf{A}\) and adds it to the set;
• Fahri chooses integer \(\mathbf{A}\) and passes it to Sinan who finds integer \(B\) in the set such that integer \(\mathbf{A} \oplus \mathbf{B}\) contains minimal possible number of 1s in its binary representation. Here \(\oplus\) is a bitwise exclusive or operation, for more details check Wikipedia page.

Your taks is to help Sinan finding minimal possible number of 1 bits in binary representaion of \(\mathbf{A} \oplus \mathbf{B}\).

Input

The first line contains integer \(\mathbf{N}\). Each of the following \(\mathbf{N}\) lines describes an event as two integers \(\mathbf{T}\) and \(\mathbf{A}\) separated by a single space. Here \(\mathbf{T}\) is an event type.

Output

For each event of the second type print the corresponding minimal number of 1 bits in a separate line.

Constraints

• \(2 <= \mathbf{N} <= 2 \cdot 10^5\),
• \(1 <= \mathbf{T} <= 2\),
• \(0 <= \mathbf{A} <= 10^6\),
• in the first event \(\mathbf{T} = 1\).

Example

Input

4
1 2
2 1
1 1
2 3

Output

2
1

Input

5
1 2
1 4
1 8
2 3
2 14

1
2