Alfi asked Roy to go for shopping with her. Witty Roy came up with a condition. He said, for each product of MRP (Maximum Retail Price) R, she'll have to pay minimum of all the prime factors of R and he himself will pay rest of the amount. Without giving it a second thought Alfi agreed.

Now they bought N number of products. You're to find how much money did Roy had to pay for each product.

Input:

First line will contain integer N, number of products they bought.

Next N lines each will contain R, MRP of each product.

Output:

Print single integer in a new line, the amount of money Roy had to pay for each product.

Constraints:

2<=N,R<=1000000

Warning: Large I/O. Be careful with certain languages.