Let's come out of codona chain for a while and have some fun.So 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 those 40 equal parts to 40 thieves and silently take the coins with him that are left after sharing.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. You have to print the number of coins Alibaba get after sharing the coins equally to theives. 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
If 125 gold coins are there in the treasury then he will give 3 coins each to all 40 thieves and takes 5 coins remaining.
In second test case 81 gold coins are there in the treasury. So he will give 2 gold coins each all 40 thieves and take 1 left in the treasury
In third test case too Out of 41 gold coins he will give 1 gold coin to each thief and take 1 left.
