D1. Looks Divisible To Me
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a positive integer $$$n$$$, we say that a positive integer $$$x$$$ is $$$n$$$-mersenne if and only if $$$2^x - 1$$$ divides $$$2^n - 1$$$.

Find all $$$n$$$-mersenne positive integers.

Input

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

Each test case contains one line of one integer $$$n$$$ ($$$1 \le n \le 10^9$$$), the integer described in the problem.

Output

For each test case containing an integer $$$n$$$, let $$$x_1, x_2, \dots, x_k$$$ (for some positive integer $$$k$$$) be all distinct $$$n$$$-mersenne positive integers where $$$x_1 \lt x_2 \lt \dots \lt x_k$$$. Output $$$x_1, x_2, \dots, x_k$$$ space-separated in ascending order.

It is guaranteed that the sum of $$$k$$$ over all test cases would not exceed $$$2 \cdot 10^6$$$.

Example
Input
3
1
4
6
Output
1
1 2 4
1 2 3 6
Note

In the first test case, we note that $$$2^1 - 1 = 1$$$, and only $$$1$$$-mersenne number if $$$1$$$ itself.

In the second test case, we note that $$$2^4 - 1 = 15$$$, and the divisors of $$$15$$$ are $$$1, 3, 5, 15$$$, making the $$$4$$$-mersenne numbers only $$$1, 2$$$, and $$$4$$$, since $$$2^1 - 1 = 1$$$, $$$2^2 - 1 = 3$$$, and $$$2^4 - 1 = 15$$$, all of which are divisors of $$$15$$$.

In the third test case, we note that $$$2^6 - 1 = 63$$$, and the divisors of $$$63$$$ are $$$1, 3, 7, 9, 21, 63$$$, and of those, the $$$6$$$-mersenne numbers are only

  • $$$1$$$ since $$$2^1 - 1 = 1$$$
  • $$$2$$$ since $$$2^2 - 1 = 3$$$
  • $$$3$$$ since $$$2^3 - 1 = 7$$$
  • $$$6$$$ since $$$2^6 - 1 = 63$$$