#1098 라그랑쥐 수

39  1 s   128 MB  

Description

양의 정수는 많아야 4 개의 제곱수의 합으로 표현가능하다는 것이 1770 년에 Joseph-Louis Lagrange 에 의해서 처음 발표되었다. 이는 Lagrange's Four-Square 이론으로 얄려져 있다.

우리가 관심있는 것은 양의 정수가 주어질 때 제곱수의 합으로 만들수 있는 종류가 몇 개가 되는 지를 구하는 것이 문제이다. 제곱수는 최대 4 개까지 사용가능하다.

가지수를 헤아릴 때 순서는 고려하지 않는다. 따라서, 42 + 32 과 32 + 42 은 같은 표현으로 본다.

예를 들어 , n 이 25 인 경우 3 가지 표현이 가능한다.

25=12 + 22 + 22 + 42
25=32 + 42
25=52

Input

입력은 여러개의 테스트 케이스로 이뤄지며, 입력의 첫번째 줄에는 테스트 케이스의 개수 T(1<=T<=255)이 입력된다.

각 테스트 케이스는 한줄로 주어지며, 2^15 이하인 양의 정수가 입력으로 주어진다.

Output

각 테스트 케이스에 대해 가능한 가지수를 한줄에 하나씩 출력한다.

Sample Input

Sample Output

2
1
25
1
3