Недавно Вова нашел \(n\) фантиков от конфет. Он помнит, что он покупал \(x\) конфет в первый день, \(2x\) конфет во второй день, \(4x\) конфет в третий день, \(\dots\), \(2^{k-1} x\) конфет в \(k\)-й день. Но есть проблема: Вова не помнит ни \(x\), ни \(k\), но он уверен, что \(x\) и \(k\) — положительные целые числа и \(k > 1\).
Вова будет удовлетворен, если вы назовете ему любое положительное целое число \(x\) такое, что существует целое число \(k>1\), при котором \(x + 2x + 4x + \dots + 2^{k-1} x = n\). Гарантируется, что существует как минимум одно решение. Обратите внимание: \(k > 1\).
Вам нужно ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Выведите одно целое число — любое положительное целое значение \(x\) такое, что существует целое число \(k>1\), при котором \(x + 2x + 4x + \dots + 2^{k-1} x = n\).
Примечание
В первом наборе тестовых данных примера одним из возможных ответов является \(x=1, k=2\). Тогда \(1 \cdot 1 + 2 \cdot 1\) равняется \(n=3\).
Во втором наборе тестовых данных примера одним из возможных ответов является \(x=2, k=2\). Тогда \(1 \cdot 2 + 2 \cdot 2\) равняется \(n=6\).
В третьем наборе тестовых данных примера одним из возможных ответов является \(x=1, k=3\). Тогда \(1 \cdot 1 + 2 \cdot 1 + 4 \cdot 1\) равняется \(n=7\).
В четвертом наборе тестовых данных примера одним из возможных ответов является \(x=7, k=2\). Тогда \(1 \cdot 7 + 2 \cdot 7\) равняется \(n=21\).
В пятом наборе тестовых данных примера одним из возможных ответов является \(x=4, k=3\). Тогда \(1 \cdot 4 + 2 \cdot 4 + 4 \cdot 4\) равняется \(n=28\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3
6
7
21
28
999999999
999999984
|
1
2
1
7
4
333333333
333333328
|