11413번 - Primes 스페셜 저지다국어

문제

Define a mass split operation for the multiset of positive integers K: for each integer k_i in the multiset we will replace it with the pair d_i and k_i/d_i, where d_i is the random integer divisor of k_i, which is greater than 1, and less than k_i. If k_i is prime, it remains untouched. All divisors can be chosen equiprobably.

For example, let’s take the multiset {2, 10, 12, 12}. Then {2, 2, 3, 3, 4, 4, 5}, {2, 2, 2, 3, 4, 5, 6} and {2, 2, 2, 2, 5, 6, 6} will be the possible outcomes of the first mass split (first and third with probability 0.25, second with probability 0.5), and {2, 2, 2, 2, 2, 2, 3, 3, 5} will be the only possible outcome of the second mass split.

If we start with a multiset containing one integer N, find the expected number of mass splits needed to obtain a multiset with prime numbers only, where the expected number is the probability-weighted average of all possible values.

입력

First line of the input contains integer T (1 ≤ T ≤ 10⁴) – number of test cases. Each test case consists of one integer N – the starting multiset (2 ≤ N ≤ 10¹⁰).

출력

For each test case, print one number – the expected number of mass splits, with absolute or relative error not worse than 10^-6.

제한

힌트