Week-2
Angry Mathematician (100 Marks) Mr. Magma is a famous mathematician and has won the Abel Prize this year for his contribution. For years, he has been doing great work in the field of Mathematics. Recently, he has discovered the Magma Numbers and has got a lot of attention all around the world.
Magma Numbers are those numbers which can be presented by multiplying the cube of a number X with another number Y.
There is a lot of talk on the Internet about Magma numbers. The trollers are also active on the Internet and are trying to give a hit to the reputation of Mr. Magma. Bantai is one of them and has slammed Mr. Magma badly. This has made Mr. Magma angry and he has decided to teach him a lesson.
Mr. Magma has challenged Bantai to tell him the count of all Magma numbers upto N (including). If Bantai fails to answer correctly, he will have to publish a public apology in Newspaper and will pledge to never troll anybody again.
Bantai tried a lot and has put his best efforts to answer Mr. Magma but obviously, he has not been successful. He has learned the lesson Mr. Magma wanted to taught and is ashamed of his act. He has already removed all comments slamming Mr. Magma and has understood the hard work put by him.
Bantai is ready to publish a public apology but also wants to get the correct answers. He wishes to learn it for his knowledge and also to save some of his embarrassment. He has heard about your Mathematics skills and wants you to help him.
Can you provide Bantai with the correct count of Magma Numbers ?
Input Format The first line of input consists of number of test cases, T
Next T lines of input consists of an integer, N.
Constraints 1<= T <= 30
1<= N <=10^18 (1e18)
Output Format For each test case, print the required output in a separate line.
Sample TestCase 1 Input 3 8 20 7 Output 1 2 0 Explanation
Test Case 1:
M = Cube of (X) * Y
The only number which can be presented in this way is 8.
M = 8 = Cube of (2) * 1
where X = 2 and Y = 1
Test Case 2:
There are 2 Magma Numbers upto 20.
M = 8, can be represented as Cube of (2) * 1
where X = 2 and Y = 1
M = 16, can be represented as Cube of (2) * 2
where X = 2 and Y = 2
Test Case 3:
There is no Magma Number upto 7 which can be presented in the Magma form.
Time Limit(X): 1.00 sec(s) for each input. Memory Limit: 512 MB Source Limit: 100 KB Allowed Languages: C, C++, C++11, C++14, C#, Java, Java 8, Kotlin, PHP, PHP 7, Python, Python 3, Perl, Ruby, Node Js, Scala, Clojure, Haskell, Lua, Erlang, Swift, VBnet, Js, Objc, Pascal, Go, F#, D, Groovy, Tcl, Ocaml, Smalltalk, Cobol, Racket, Bash, GNU Octave, Rust, Common LISP, R, Julia, Fortran, Ada, Prolog, Icon, Elixir, CoffeeScript, Brainfuck, Pypy, Lolcode, Nim, Picolisp, Pike, pypy3