Sunaina asked Joy whether he would go shopping with her. Joy being witty came up with a condition.
He said that for each product she buys having MRP (Maximum Retail Price) 'P', she will have to pay minimum of all the prime factors of P and the rest of the amount he himself would pay. Sunaina agreed without giving it a second thought.
Now they bought N number of products. You have been given a task to find how much money did Joy had to pay for each product.
Input Format:
First line will contain an integer 'N', number of products they bought.
Next N lines each will contain 'P', the MRP of each product.
Output Format:
Print the amount of money Joy had to pay for each product 'N'.
Constraints:
1 ≤ N ≤ 10^3
2 ≤ P ≤ 10^5
For Test Case 1: Only 1 prime factor of 7 is 7 itself, so Sunaina will pay all the money and hence Joy has to pay 0.
For Test Case 2: Prime Factors of 10 are 2 and 5, minimum of these is 2, so Sunaina pays 2 and hence Joy has to pay the rest, which is 8.
For Test Case 3: Least prime factor for number 999 is 3, so Sunaina pays 3 Rs. and Joy has to pay 996 Rs.
