Every one knows Alibaba and 40 thieve's story. Now let's modify this story a little. Alibaba saw 40 thieves fighting with each other to share the treasure they've stolen equally. Alibaba stops them and decided to share the treasure to all the 40 thieves equally.

But he is wise enough to fool them. He divides the treasury into 40 maximum equal parts and share 40 equal parts to 40 thieves and take another part left with him silently.He makes sure thieves that they all got equal parts. The thieves don't care about whether the sum of all equal parts with them is equal to initial treasury or not.It is assured that Alibaba will divide the equal parts with maximum number of gold coins.So that thieves won't doubt him.Consider the sample input/output for more details.

Input:
First line contains integer T denoting number of test cases.
Next T lines contains a integer n denoting the number of gold coins in the treasury.
Output:
Print T integers in each line denoting the number of gold coins Alibaba will get after sharing equal parts to the thieves.

Constraints:
1 ≤ T ≤ 10
0 ≤ n ≤ 100000
Sample Input1:
3
125
81
42
Sample Output1:
5
1
2