ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2167. Cipher Message 5

Time limit: 2.0 second
Memory limit: 256 MB
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 10012 and 01012 will be 11002.
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.

Input

The first line contains an integer T — the number of numbers in the message from the headquarters (1 ≤ T ≤ 105).
The next T lines contain one integer each ai — the numbers from the message (0 ≤ ai ≤ 1 048 575).

Output

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.

inputoutput
```3
5
6
1
```
```0
1
2
```