# Count the Factorials

Ram is a bright boy who is very much interested in number theory. He was studying about factorials of numbers, and got some interesting idea. Being a brilliant coder, he started writing a program and implemented the following routines : • fact(n) — This function returns the value of n!, where n ≥ 0 eg. fact(5) returns 120 • count(n) — This function returns the number of terms in the prime factorisation of n, where n ≥ 0. eg. count(24) returns 4 (because, 24 = 2 ∗ 2 ∗ 2 ∗ 3). The prime factorisation of 24 contains 4 terms • func(n) — This function is explained below. Ram wrote the function “func” as follows: int func(int \$n\$) { int ans = 0; for(int \$i=0\$; ; \$i++\$) { if( count( fact( \$i\$ ) ) \$\le n\$) ans++; else return ans; } } The above procedure takes too much time to execute. Help Ram by writing a more efficient solution that does the same function as “func” does. Input The first line of input gives the number of test cases t. The next t lines contains a positive integer, representing n (1 ≤ t ≤ 1000, 1 ≤ n ≤ 10000000). Output Print func(n) for the given n, on a line by itself. Note: Consider 1 as a prime number. Sample Input 4 1 2 3 4

2/2 Sample Output 3 4 4 5