There are n children who have landed up in an unknown place where they find just some jar of cookies to eat. They also have a dog with them. The children gather all the cookies and put them in a big jar. Exhausted, they agree to go and wait until the next morning to divide up the cookies.
At one o'clock in the morning, the first child wakes up. He realizes that he can't trust the others, and decides to take his share now. He divides the cookies into n equal shares, but there is one left over. He gives that cookie to the dog, hides his cookies, and puts the rest of the cookies back.
At two o'clock, the second child wakes up. Not realizing that the first child has already taken his share, he too divides the cookies up into n shares, leaving one over which he gives to the dog. He then hides his share, and puts the remainder back.
At three, four, five…… ‘n’ o'clock in the morning, the third, fourth, fifth …….nth children each wake up and carry out the same actions.
In the morning, all the children wake up, and try to look innocent. No one makes a remark about the diminished share of cookies, and no one decides to be honest and admit that they've already taken their share. Instead, they divide the share up into nshares, for the (n+1)th time, and find that there is yet again one cookie left over, which they give to the dog. You have to find out how many cookies were present originally in the jar.

Input

The input will contain several numbers of test cases. The first line will contain the number of test cases(x) followed by ‘x’ lines of inputs which contains the values of ‘n’.

Output

For each input print the number of cookies present in the jar.

Example

Input:
2
5
6

Output:
15621
279931

见题面

见题面