G. 舌切雀（Hard Version）
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

这是该问题的 Hard 版本，它与 Easy 版本的唯一区别是在本题中 $$$n\le{10^{18}}$$$ 。

令 $$$f(x) = \begin{cases} 0 &\text{if }\forall k(k\in{\mathbb{N}\land k \gt 1})\to x^{\frac{1}{k}}\notin {\mathbb{Q}} \\ 1 &\text{if } \exists k(k\in{\mathbb{N}\land k \gt 1})\to x^{\frac{1}{k}}\in {\mathbb{Q}} \end{cases}$$$

求 $$$ \sum_{i=1}^{n} f(i) $$$。

其中 $$$\mathbb{N}$$$ 代表自然数集， $$$\mathbb{Q}$$$ 代表有理数集。

Input

输入一个正整数 $$$T$$$ $$$(1\le{T}\le{2\times{10^3}})$$$ ，代表测试组数。

随后 $$$T$$$ 行，每行包含一个正整数 $$$n$$$ $$$(1\le{n\le{10^{18}}})$$$ 。

Output

输出 $$$T$$$ 行，每行包含一个整数代表答案。

Example
Input
2
5
13
Output
2
4