#P1343A. Candies
-
ID: 5322
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Candies
No submission language available for this problem.
Description
Recently Vova found $n$ candy wrappers. He remembers that he bought $x$ candies during the first day, $2x$ candies during the second day, $4x$ candies during the third day, $\dots$, $2^{k-1} x$ candies during the $k$-th day. But there is an issue: Vova remembers neither $x$ nor $k$ but he is sure that $x$ and $k$ are positive integers and $k > 1$.
Vova will be satisfied if you tell him any positive integer $x$ so there is an integer $k>1$ that $x + 2x + 4x + \dots + 2^{k-1} x = n$. It is guaranteed that at least one solution exists. Note that $k > 1$.
You have to answer $t$ independent test cases.
The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.
The only line of the test case contains one integer $n$ ($3 \le n \le 10^9$) — the number of candy wrappers Vova found. It is guaranteed that there is some positive integer $x$ and integer $k>1$ that $x + 2x + 4x + \dots + 2^{k-1} x = n$.
Print one integer — any positive integer value of $x$ so there is an integer $k>1$ that $x + 2x + 4x + \dots + 2^{k-1} x = n$.
Input
The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.
The only line of the test case contains one integer $n$ ($3 \le n \le 10^9$) — the number of candy wrappers Vova found. It is guaranteed that there is some positive integer $x$ and integer $k>1$ that $x + 2x + 4x + \dots + 2^{k-1} x = n$.
Output
Print one integer — any positive integer value of $x$ so there is an integer $k>1$ that $x + 2x + 4x + \dots + 2^{k-1} x = n$.
Samples
7
3
6
7
21
28
999999999
999999984
1
2
1
7
4
333333333
333333328
Note
In the first test case of the example, one of the possible answers is $x=1, k=2$. Then $1 \cdot 1 + 2 \cdot 1$ equals $n=3$.
In the second test case of the example, one of the possible answers is $x=2, k=2$. Then $1 \cdot 2 + 2 \cdot 2$ equals $n=6$.
In the third test case of the example, one of the possible answers is $x=1, k=3$. Then $1 \cdot 1 + 2 \cdot 1 + 4 \cdot 1$ equals $n=7$.
In the fourth test case of the example, one of the possible answers is $x=7, k=2$. Then $1 \cdot 7 + 2 \cdot 7$ equals $n=21$.
In the fifth test case of the example, one of the possible answers is $x=4, k=3$. Then $1 \cdot 4 + 2 \cdot 4 + 4 \cdot 4$ equals $n=28$.