# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Tareq, SOD & Prime

By mohibur · 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


### Statistics

61% Solution Ratio

YouKnowWhoEarliest, 6M ago

YouKnowWhoFastest, 0.3s

moursalinmeLightest, 20 MB

moursalinmeShortest, 986B