Số  hoàn hảo là số nguyên dương có tổng các ước số nguyên dương bé hơn nó bằng chính nó.Bài toán cho các bạn là hãy liệt kê tất cả các số hoàn thiện nhỏ hơn số n.

Input

dòng đầu là k số bộ test

          K dòng tiếp theo là số n(0<n<10⁹)

Output

K dòng mỗi dòng là các số hoàn thiện nhỏ hơn n(mỗi số cách nhau 1 dấu cách).

Example

Input:
1
100
Output:
6  28