#P1958A. 1-3-5
1-3-5
Description
In Berland, coins of worth , and burles are commonly used (burles are local currency).
Eva has to pay exactly burles in a shop. She has an infinite amount of coins of all three types. However, she doesn't like to pay using coins worth burle — she thinks they are the most convenient to use.
Help Eva to calculate the minimum number of coins worth burle she has to use, if she has to pay exactly burles. Note that she can spend any number of coins worth and/or burles.
The first line contains one integer () — the number of test cases.
Each test case consists of one line, containing one integer ().
For each test case, print one integer — the minimum number of -burle coins Eva has to use.
Input
The first line contains one integer () — the number of test cases.
Each test case consists of one line, containing one integer ().
Output
For each test case, print one integer — the minimum number of -burle coins Eva has to use.
Note
In the first test case, Eva should use coin worth burle, and coins worth burles.
In the second test case, Eva should use coin worth burles and coin worth burles.
In the third test case, Eva should use coins worth burles.
In the fourth test case, Eva should use coins worth burle.
In the fifth test case, Eva should use coins worth burles and coin worth burles.