Given a four-digit integer n, your task is to count the number of ways to make it a square number by changing exactly one digit (note that you can’t change the first digit to 0). For example, if n = 7844, there are two ways: 3844 = 622 and 7744 = 882. Input The first line of integer contains one integer T (1 ≤ T ≤ 1000), the number of test cases. Each test case contains a single integer n (1000 ≤ n ≤ 9999). Output For each test case, print the case number and the number of ways to make it a square integer by changing exactly one digit. Sample Input 2 7844 9121 Sample Output Case 1: 2 Case 2: 0