Count the Numbers

Time Limit: 2 sec

 

The Problem

You all are knows about GCD (Greatest Common Divisor).  This is simple problem for all math lovers. In this problem I will give you a number N. You have to count those numbers which will fulfills the following rule.

Rule: GCD(P,N) = P, means GCD of two numbers P and N is must be equals to  P(1<=P< N).

 

The Input

The input Starts with an integer T (1<=T<=100) the number of test cases. The next T lines will contains a single positive integer N (2<=N<=10^14).

 

The Output

For each case print the counted total numbers of P which fulfill the rule described above. You have to give the output in sample format shown in sample output.

 

Sample Input

4

5

10

36

1000

 

Sample Output

Case 1# 1

Case 2# 3

Case 3# 8

Case 4# 15

 

 

 

[Outsbook Round #2 Online Contest]

Problem Setter: Milton Deb