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