Limits 1s, 512 MB

Tareq loves Prime Number. A prime Number is a number that is only divisible by 1 and the number itself. He also loves to find out the sum of divisors of a number. One day he thought about a problem related to prime number and SOD(Sum of Divisors). Can you solve this problem?

In this Problem, we define two functions as follows:

  1. SOD(N) = Sum of divisors of an integer number N. For Example: SOD(6) = 1 + 2 + 3 + 6 = 12.
  2. SSOD(N) = For each divisor of N, calculate sum of their SOD. For Example: SSOD(6) = SOD(1) + SOD(2) + SOD(3) + SOD(6) = 1 + 3 + 4 + 12 = 20.

You are given a number N. You have to find how many prime numbers are there within SOD(N) and SSOD(n) inclusively.

Constraints:

1 ≤ T ≤ $3×10^{5}$

1 ≤ N ≤ $10^{6}$

Input

Input starts with an integer T denoting the number of test cases. Each case contains one integer N.

Output

For each case of input print the case number and then print one integer which is described in the description.

Sample

InputOutput
2
6
8
Case 1: 3
Case 2: 3

Submit

Login to submit.

Statistics

64% Solution Ratio
YouKnowWhoEarliest, Oct '20
nusuBotFastest, 0.2s
wajiulLightest, 20 MB
moursalinmeShortest, 986B
Toph uses cookies. By continuing you agree to our Cookie Policy.