Funny game#3240

Funny game

5 seconds
256 megabytes
Easy

A group of students gathered to celebrate a successfully passed exam on algorithms. But they forgot to buy the most important thing to celebrate — a celebration cake, and now they need to choose someone who will go to the store for the cake. Since no one wanted to do it voluntarily, they decided to make a choice with the following game.

In the plane draw a complete graph with vertices, numbered from to , initially the chip is located at the first vertex. Each player must pass the chip through all vertices of the graph, visiting each only once and return to the starting position, each path can be used only once per game (different routes are those which differ in the order of visiting vertices). The one who cannot build a path is considered chosen by the game and goes for the cake. The students played in turns, and it is known that the cake was fetched by the -th player. Your task is to determine what the smallest number of students could be in a group, if you know that there were at least .

Input

The first line of the input file contains the number of tests (1 \le t \le 1000). Each test consists of a single number (1 \le m \le 10^{18}).

Output

For each test case output a single line with only one number that is the answer to the problem.

Examples

Example 1

Loading
Loading