Với mỗi số nguyên ~n~ cho trước, bạn hãy đếm số cặp số ~(a, b)~ (~a, b~ chẵn; ~a, b > 0~) sao cho ~a \cdot a \cdot b \cdot b = n~.

Lưu ý: Cặp ~(a, b)~ có kể thứ tự. Ví dụ, ~(1, 2)~ và ~(2, 1)~ là hai cặp số khác nhau.

Input

• Dòng đầu tiên gồm số nguyên dương ~t~ ~(1 \le t \le 20)~ — số bộ test.

• ~t~ dòng tiếp theo, mỗi dòng gồm một số nguyên dương ~n~ ~(0 < n \le 10^{18})~.

Output

• In ra ~t~ dòng, mỗi dòng gồm một số nguyên là số cặp thoả mãn.

Scoring

Sample Input 1

2
144
72

Sample Output 1

2
0

Notes

• Trong testcase thứ 1, các cặp số thoả mãn là: ~(2, 6)~, ~(6, 2)~.

• Trong testcase thứ 2, không tồn tại cặp số thoả mãn.