You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

定义美妙的函数

$$\begin{array}{} F(x)= \left\{\begin{matrix} 0,{x\leq2}\\ 1,x> 2\text{且}x\text{为质数} \\ \sqrt{x},x> 2\text{且} x\text{为完全平方数} \\0,\text{otherwise} \end{matrix}\right. \end{array}$$

定义序列 $A$ 的价值为所有 $F(A_i)$ 的和，也就是 $\sum_{i=1}^{|A|} F(A_i)$。

请输出所有和为 $n$ 的正整数序列 $A$ 的最大价值。

输入格式

第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 行，每行一个正整数 $n$。

输出格式

接下来 $T$ 行，输出该组数据的答案。

样例 #1

样例输入 #1

2
1
6

样例输出 #1

0
2

提示

样例解释

• 第一组询问 $n=1$，只有一种方案为 $A=[1]$。
• 第二组询问 $n=6$，一种方案为 $A=[3,3]$。

对于 $10\%$ 的数据，$n\le 10$。

对于 $30\%$ 的数据，$n\le 10^3$。

对于 $50\%$ 的数据，$n\le 10^6$。

对于 $70\%$ 的数据，$n\le 10^9$。

对于 $100\%$ 的数据，$1\le T\le 10^5,1\le n\le 10^{18}$。