beecrowd | 2596

Xenlonguinho

By Aline Regina de Oliveira, IFSULDEMINAS Brazil

Timelimit: 1

Kogu is searching for the dragon spheres to summon Xenlonguinho and ask him to relive his friend Kuriri, who unfortunately died in the last battle of Z's warriors.

However Kogu is having a great deal of trouble finding the spheres, so Xenlonguinho, who is his known for a long time, decided to make an exception and agreed to be invoked in case Kogu finds all spheres whose number of divisors of the number of stars in the sphere are even.

For example if there are seven spheres, Kogu would not have to find the one- and four-star spheres because they have an odd number of divisors, so he only needs to take 5 spheres to summon Xenlonguinho.

As Koku is not very good at calculations, he asked you to write a program that given the total of existing balls, show the minimum amount of spheres he needs to look for.

Input

The first line contains an integer C that represents the number of test cases. Next lines contain an integer N (2 ≤ N ≤ 1000) representing the amount of spheres required to invoke Xenlonguinho.

Output

Your program should display the minimum amount of spheres Kogu has to look for.

 Input Sample Output Sample 1 7 5