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×1053×10^{5}

1 ≤ N ≤ 10610^{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

    Discussion

    Statistics


    61% Solution Ratio

    YouKnowWhoEarliest, 6M ago

    YouKnowWhoFastest, 0.3s

    moursalinmeLightest, 20 MB

    moursalinmeShortest, 986B

    Submit

    Login to submit