Với một số nguyên \(n\), Alice quan tâm đến các ước nguyên dương của \(n^2\) thỏa mãn điều kiện: nhỏ hơn \(n\) và không phải là ước của \(n\).

Yêu cầu: Cho số nguyên dương \(m\), xét số \(n = m \cdot (m + 1) \cdot (m + 2)\), hãy giúp Alice đếm số ước nguyên dương của \(n^2\) thỏa mãn điều kiện: nhỏ hơn \(n\) và không phải là ước của \(n\).

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu;
• \(T\) dòng sau, mỗi dòng chứa một số nguyên dương \(m\).

Output

• Gồm \(T\) dòng, mỗi dòng là số ước của \(n^2\) thỏa mãn: nhỏ hơn \(n\) và không phải là ước của \(n\).

Example

2
1
2

1
3

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(m \le 10^3; T \le 10;\)
• Subtask \(2\) (\(25\%\) số điểm): \(m \le 10^6; T \le 10;\)
• Subtask \(3\) (\(25\%\) số điểm): \(m \le 10^6; T \le 10^3;\)
• Subtask \(4\) (\(25\%\) số điểm): \(m \le 10^6; T \le 10^5;\)