Với mỗi số nguyên ~n~ cho trước, bạn hãy đếm số cặp ~(a, b)~ (~a, b~ chẵn, ~a, b > 0~) sao cho ~a . a . b . 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 demcap.inp

• 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 demcap.out

• 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

Note

• 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