Sum of square of two natural numbers

5

1 votes
Easy-Medium
Problem

Given a number your task is to find the number of ways in which it can be expressed as the sum of square of two natural numbers.

Input

First line contains N, denoting number of test cases. Second line contains N space separated numbers.

Output

A single number m, denoting the number of possible ways.

Sample Input

1

65

Sample Output

2

Explanation

65 = 1^2 + 8^2 = 4^2 + 7^2

Time Limit: 5
Memory Limit: 256
Source Limit:
Editor Image

?