Cho một số nguyên dương \(N\).

Yêu cầu:

• Đếm số cặp số nguyên \((x, y)\) thỏa mãn:
• \(x^2 + y = N\)
• \(y ≥ 0\)

Input

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

Output

• In ra T dòng mỗi dòng là kết quả cần tìm.

Example

2
2
9

3
7