NITHY - LUCKYNINE

Mr. Nithyanandan likes number 9 very much. So he wanted to represent any number as a sum of numbers ending with 9.

For example he represents:

  • 28 as 19+9
  • 48 as 39+9 or 19+29
  • 99 as 99 or 9+9+9+9+9+9+9+9+9+9+9

But he wants to minimize the number of summations since he’s weak in mathematics.

Input

The first line consists of an integer t representing the number of test cases. Then for next t lines each line consists of an integer n (0 <= n <= 10000).

Output

For each test case output the minimum number of summations required. If it’s impossible to represent then print Impossible.

EXAMPLE

Input:
5
28
48
99
15
1000

Output:
2
2
1
Impossible
10

Added by:cegprakash
Date:2011-05-18
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.