Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4091
Even Number Theory

Time Limit: 1 Second      Memory Limit: 65536 KB

Let $\mathbb{E} = \{2k | k \in \mathbb{Z}^+\}$, which is the set of all positive even numbers. Define the following concepts:

  • E-prime: A positive even number $p$ is an e-prime, if and only if there does not exist two integers $a$ and $b$, such that $a, b \in \mathbb{E}$ and $p = ab$. For example, 2 and 18 are e-primes, but 16 is not, as $16 = 2 \times 8$.

  • E-prime factorization: An e-prime factorization of a positive even number $e$ is the decomposition of $e$ into the product of some smaller e-primes.

    More formally, an e-prime factorization of a positive even number $e$ is a multiset (a set which allows duplicated elements) $\mathbb{P}$ such that

    • For all $p \in \mathbb{P}$, $p$ is an e-prime;
    • $\prod\limits_{p \in \mathbb{P}}p = e$.

    Please note that, different from the traditional number theory, the e-prime factorization of a positive even number $e$ is NOT unique. For example, we can factorize 36 into $2 \times 18$ or $6 \times 6$.

  • E-factorial: Let $e!!$ be the e-factorial of a positive even number $e$, we have $$e!! = \prod\limits_{k \in \mathbb{E}, k \le e}k$$

    For example, $6!! = 2 \times 4 \times 6 = 48$.

Given a positive even number $e$, your task is to find an e-prime factorization $\mathbb{P}$ of $e!!$, such that $|\mathbb{P}|$ (the size of $\mathbb{P}$) is as large as possible. In order to make the task easier, you just need to output the value of $|\mathbb{P}|$.

Input

There are multiple test cases. The first line of the input contains an integer $T$ (about 50), indicating the number of test cases. For each test case:

The first and only line contains a positive even number $e$ ($2 \le e \le 10^{1000}$), indicating the given number.

Output

For each test case output one integer in one line, indicating the maximum size of the e-prime factorization of $e!!$.

Sample Input

2
2
4

Sample Output

1
3

Hint

For the first sample test case, as 2!! = 2 is an e-prime, the answer is (obviously) 1.

For the second sample test case, we can factorize 4!! = 8 into $2 \times 2 \times 2$, which contains 3 e-primes.


Author: CHEN, Jingbang
Source: The 19th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status