Số nguyên dương \(m > 1\) được gọi là "số rất lẻ" nếu các ước dương của \(m\) (kể cả chính nó) có thể được viết lên một vòng tròn theo một thứ tự nào đó sao cho tổng của hai số đứng cạnh nhau luôn là một số lẻ.

Ngoài ra, tổng của tất cả các ước dương của \(m\) cũng phải là số lẻ.

Ví dụ, \(18\) là một số rất lẻ vì các ước của nó là: \(1, 2, 3, 6, 9, 18\). Có thể viết chúng lên vòng tròn theo thứ tự trên, khi đó tổng của hai số đứng cạnh nhau luôn là số lẻ. Đồng thời, tổng các ước của chúng cũng là số lẻ:

mà \(39\) cũng là số lẻ.

Yêu cầu: cho \(q\) truy vấn. Mỗi truy vấn gồm một số nguyên dương \(n\). Hãy in ra số lượng số rất lẻ là ước của \(n\).

Input

• Dòng đầu tiên chứa số nguyên dương \(q\) (\(q \leq 10\)) - số lượng truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\) (\(1 \leq n \leq 10^{18}\)).

Output

• Ghi ra \(q\) dòng, mỗi dòng một số nguyên duy nhất là câu trả lời cho truy vấn tương ứng.

Example

3
18
30
7

2
1
0

Subtasks

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10^3\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 10^6\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 10^{12}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.