Bob's lucky number is 6. He wanted to represent any number n given to him as sum of numbers ending with 6.

For example he represents:

• 28 as 6 + 16 + 6
• 38 as 6 + 16 + 16, or 26 + 6 + 6
• 36 as 36, or 6 + 6 + 6 + 6 + 6 + 6

He wants to find the minimum number of summations required to represent n with numbers ending with 6.

Input

The first line consists of an integer t, the number of test cases. For each test case you are given an integer n.

Output

For each test case, find the minimum number of summations required to represent n with numbers ending with 6. If it is impossible to represent, print “Impossible".

Constraints

1 <= t <= 10^6

1 <= n <= 10^4

Example

Input:
4
28
38
36
14

Output:
3
3
1
Impossible