|
B |
Race
to 1 Input: Standard Input Output: Standard Output |
|
Dilu have learned a new thing
about integers, which is - any positive integer greater than 1 can be divided by
at least one prime number less than or equal to that number. So, he is now
playing with this property. He selects a number N. And he calls this D.
In each turn he randomly chooses a
prime number less than or equal to D.
If D is divisible by the prime number
then he divides D by the prime
number to obtain new D. Otherwise he
keeps the old D. He repeats this
procedure until D becomes 1. What is
the expected number of moves required for N
to become 1.
[We say that an integer is said to
be prime if its divisible by exactly two different integers. So, 1 is not a
prime, by definition. List of first few primes are 2, 3, 5, 7, 11, …]
Input
Input will start with an integer T (T <= 1000), which indicates the number of test cases. Each of
the next T lines will contain one
integer N (1 <= N <= 1000000).
Output
For each test case output a single line giving the case number followed by the expected number of turn required. Errors up to 1e-6 will be accepted.
Sample
Input Output
for Sample Input
|
3 1 3 13 |
Case
1: 0.0000000000 Case
2: 2.0000000000 Case
3: 6.0000000000 |
Problemsetter: Md. Arifuzzaman Arif
Special Thanks: Sohel Hafiz