C. Yet Another Cool Pair Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$.

For the integer $$$n$$$, a pair $$$(a,b)$$$ is considered cool only if:

  • $$$1 \le a \lt b \le n$$$;
  • $$$a$$$ $$$\&$$$ $$$b$$$ $$$=$$$ $$$0$$$, where $$$\&$$$ denotes the bitwise AND operation.

For a given integer $$$n$$$, find the maximum value of $$$\gcd(a,b)$$$ among all cool pairs $$$(a, b)$$$. Here $$$\gcd$$$ means the greatest common divisor.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), the number of test cases.

For each test case, the only line contains a single integer $$$n$$$ $$$(2 \le n \le 10^9)$$$.

Output

For each test case, print the maximum value of $$$\gcd(a,b)$$$ for all cool pairs $$$(a, b)$$$.

Example
Input
9
2
3
4
5
6
7
8
9
10
Output
1
1
2
2
2
2
4
4
5