A Kitten on the Fence

Time limit5sMemory limit128 MB

Summary

List every hop size K from 1 to N that visits all N pickets on a circular fence before repeating.

Level: Medium4 of 10
Topics: Number theory
Solved: No attempts yet

Problem

A little kitten has climbed onto a fence and is hopping along it.

The fence is made of N pickets spaced evenly around a circle. The kitten hops along the fence K pickets at a time. For example, when N = 8 and K = 3 the kitten lands on the pickets 1, 4, 7, 2, ... in that order. The kitten keeps hopping as long as it lands on a picket it has not visited yet. The moment it lands on a picket it has already stepped on, it climbs straight down off the fence.

Given the number of pickets N, find every value of K ( $1 \le K \le N$ ) for which the kitten, hopping in the way described above, steps on every picket of the fence.

Input

The first line contains the number of test sets Z ( $1 \le Z \le 10$ ). The descriptions of the sets then follow.

Each set consists of a single line containing the natural number N ( $1 \le N \le 1000000$ ) described above.

Output

For each set, print on its own line all values of K that satisfy the condition, in increasing order. Separate adjacent numbers with a single space and do not print a trailing space at the end of the line.

Examples1

Example 1
Input
```
4
1
2
7
8
```
Expected output
```
1
1
1 2 3 4 5 6
1 3 5 7
```