← 返回题目列表

Codeforces · 1619/B

B. 正方形和立方体

中文机器翻译题面 查看原题

Polycarp 喜欢正整数的正方形和立方体。这是他喜欢的数字序列的开头:$$$1$$$、$$$4$$$、$$$8$$$、$$$9$$$、...

对于给定的数字 $$$n$$$,计算 Polycarp 喜欢的从 $$$1$$$ 到 $$$n$$$ 的整数个数。换句话说,找到这样的 $$$x$$$ 的数量,使得 $$$x$$$ 是正整数的平方或正整数的立方(或同时是平方和立方)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 20$$$) — 测试用例的数量。

然后 $$$t$$$ 行包含测试用例,每行一个。每一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^9$$$)。

输出

对于每个测试用例,打印您正在寻找的答案 - Polycarp 喜欢的从 $$$1$$$ 到 $$$n$$$ 的整数个数。

示例

输入 #1

6
10
1
25
1000000000
999999999
500000000

输出 #1

4
1
6
32591
32590
23125