[Solved] Possible ways to Propose CodeCrush by NewtonSchool

John is confused about the number of ways to propose to Olivia. So, he asked for your help. Now, you need to determine the number of ways for John to propose to Olivia.

For that, You are given an integer N and you need to count the number of pairs (x₁, x₂) such that x₁² + x₂² = N and x₁, x₂ both are positive integer.

Input

The first line contains a single integer T, the number of test cases.

T lines follow. Each line describes a single test case and contains a single integer N.

Constraints:
1 <= T <= 100
2 <= N <= 10⁵

Output

For each test case, print a single integer count of such pairs.

Example

Sample Input 1:
2
13
4

Sample Output 2:
2
0

Solution

import java.io.*; // for handling input/output
import java.util.*; // contains Collections framework

// don't change the name of this class
// you can add inner classes if needed
class Main {
    public static void main (String[] args) {
        // Your code here
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            int count = 0;
            for(int i=1;i<=Math.sqrt(n);i++){
                int j = n-i*i;
                if(j>0 && Math.sqrt(j)==(int)Math.sqrt(j)){
                    count++;

                    // sauravhathi
                }
            }
            System.out.println(count);
        }
    }
}

Happy Learning – If you require any further information, feel free to contact me.