Little Syed loves brute force. He thinks that brute force can be the solution to any problem in the world. You give him any question, and he'll have a brute force answer ready for you, almost all the time. His good friend Little Jhool (Like, always!) decides to teach him a lesson, by giving him problems which cannot be solved by brute force, because he wants Syed to learn algorithms.

• Given a number, n, Syed needs to find the number closest to n, though less than n which satisfies Jhool's swinging theorem.

Jhool's swinging Theorem: A number n, such that it can be expressed as a sum of two positive algebraic cubes; AND, if that number can be expressed in such a manner in more than one way - it satisfies the theorem.

Now, everyone here on HackerEarth knows how much we hate Little Jhool (No, not really!) - so we want you to help Syed in figuring out Jhool's queries - once and for all!

Input Format:
The first line contains an integer, t - denoting the number of test cases.

The next t lines will contain, an integer - n - denoting the number which Jhool gives.

Output Format:
You have to print the previous number satisfying the given constraints. If no such previous number exists, print -1.

Constraints:
1 <= t <= 100
1 <= n <= 704977