Stierlitz received T numbers from the headquarters. “Cipher Message,” thought Müller. “Prime numbers,” thought Stierlitz. But it’s not that simple!

For encryption, the headquarters uses the bitwise exclusive OR operation. Let’s say there are two numbers, represented in binary form. The result of this operation will be a number, where each bit of the binary representation is the result of the exclusive OR operation of the corresponding positions of the two given numbers: for bits “0” and “0” or bits “1” and “1”, the result is “0”, and for bits “0” and “1” or bits “1” and “0”, the result is “1”. For example, the result of the bitwise exclusive OR operation on the numbers 1001₂ and 0101₂ will be 1100₂.

The headquarters takes a prime number and another non-negative integer (encryption key), applies the bitwise exclusive OR operation between them, and thus obtains the result. However, the encryption keys can be different for different numbers. But there is one problem — Stierlitz forgot the encryption keys of the headquarters and therefore cannot decrypt any of the numbers! However, after some thinking, Stierlitz realized that he can apply the operation used by the headquarters once again to obtain prime numbers. Now, for each of the numbers in the message, he needs to find the smallest possible key that, when used in the operation, will result in a prime number.

Müller is already on the way, so Stierlitz asked for your help with this important task.

The first line contains an integer T — the number of numbers in the message from the headquarters (1 ≤ T ≤ 10⁵).

The next T lines contain one integer each a_i — the numbers from the message (0 ≤ a_i ≤ 1 048 575).

Output T non-negative integers, each on a new line — the smallest encryption key for each of the encrypted numbers in the order of input.