偶数论 - Problem

令 $E = \{2k \mid k \in \mathbb{Z}^+\}$，即所有正偶数的集合。定义以下概念：

E-素数 (E-prime)：一个正偶数 $p$ 是 E-素数，当且仅当不存在两个整数 $a$ 和 $b$，满足 $a, b \in E$ 且 $p = ab$。例如，2 和 18 是 E-素数，但 16 不是，因为 $16 = 2 \times 8$。
E-素因数分解 (E-prime factorization)：一个正偶数 $e$ 的 E-素因数分解是指将 $e$ 分解为若干个较小的 E-素数的乘积。

更正式地，一个正偶数 $e$ 的 E-素因数分解是一个多重集（允许重复元素的集合）$P$，满足：
- 对于所有 $p \in P$，$p$ 是一个 E-素数；
- $\prod_{p \in P} p = e$。
请注意，与传统数论不同，正偶数 $e$ 的 E-素因数分解不是唯一的。例如，我们可以将 36 分解为 $2 \times 18$ 或 $6 \times 6$。
E-阶乘 (E-factorial)：设 $e!!$ 为正偶数 $e$ 的 E-阶乘，我们有：

$$e!! = \prod_{k \in E, k \le e} k$$

例如，$6!! = 2 \times 4 \times 6 = 48$。

给定一个正偶数 $e$，你的任务是找到 $e!!$ 的一个 E-素因数分解 $P$，使得 $|P|$（$P$ 的大小）尽可能大。为了简化任务，你只需要输出 $|P|$ 的最大可能值。

输入包含多组测试数据。输入的第一行包含一个整数 $T$（大约 50），表示测试数据的组数。对于每组测试数据：

第一行也是唯一的一行包含一个正偶数 $e$（$2 \le e \le 10^{1000}$），表示给定的数字。

对于每组测试数据，在一行中输出一个整数，表示 $e!!$ 的 E-素因数分解的最大大小。

2
2
4

1
3

对于第一个样例测试数据，由于 $2!! = 2$ 是一个 E-素数，答案（显然）是 1。

对于第二个样例测试数据，我们可以将 $4!! = 8$ 分解为 $2 \times 2 \times 2$，其中包含 3 个 E-素数。

QOJ.ac