By Leonardo Blanger, URI Brazil
Christmas is comming, and Santa needs to evaluate how well each kid behave along the year, in order to define how many gifts each one of them are going to receive this year. The avaliation works in very strange way:
First, the Santa's assistants, capable of observing all the kids in the world, will assign to each kid an integer number N. Then, the number of gifts a kid receives is equal to N-D, where D is the greatest divisor of N, differente than N.
Planing to cheat in the distribution of the gifts to bennefit of some kids, a group of assistants decided to change the process. In the new version, the value N is subdivided int Q "parts", each being ni (1 < ni), in a way that N = Σni, (1 ≤ i ≤ Q), and the number of gifts is calculated individually for each of these parts. The total number of gifts a kid receives in this new aproach is equal to the sum of the number of gifts for all the values ni.
Your task is, given the avaliation N for each kid, help the assistants to perform this division in order to maximize the number of gifts each kid receives. Note that the assistants are free to define the number of parts Q, as well as the value of each of the individual parts, as long as they add up to N.
Input consists of the value N for a number of kids. (1 < N ≤ 1010)
For each kid, print the maximum number of gifts that this kid can receive, considering the choice for the value of Q and the subdivision are done in an optimal way.
|Input Sample||Output Sample|