#P1958A. 1-3-5

1-3-5

Description

In Berland, coins of worth 11, 33 and 55 burles are commonly used (burles are local currency).

Eva has to pay exactly nn 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 11 burle — she thinks they are the most convenient to use.

Help Eva to calculate the minimum number of coins worth 11 burle she has to use, if she has to pay exactly nn burles. Note that she can spend any number of coins worth 33 and/or 55 burles.

The first line contains one integer tt (1t1001 \le t \le 100) — the number of test cases.

Each test case consists of one line, containing one integer nn (1n1001 \le n \le 100).

For each test case, print one integer — the minimum number of 11-burle coins Eva has to use.

Input

The first line contains one integer tt (1t1001 \le t \le 100) — the number of test cases.

Each test case consists of one line, containing one integer nn (1n1001 \le n \le 100).

Output

For each test case, print one integer — the minimum number of 11-burle coins Eva has to use.

样例输入 1

5
7
8
42
2
11

样例输出 1

1
0
0
2
0

Note

In the first test case, Eva should use 11 coin worth 11 burle, and 22 coins worth 33 burles.

In the second test case, Eva should use 11 coin worth 33 burles and 11 coin worth 55 burles.

In the third test case, Eva should use 1414 coins worth 33 burles.

In the fourth test case, Eva should use 22 coins worth 11 burle.

In the fifth test case, Eva should use 22 coins worth 33 burles and 11 coin worth 55 burles.