Gang members of unseen gang are trying to plant the bomb in the different sectors of the city, but they need approval from the leader of unseen gang. To get approval they need to send the sector number in which they wants to plant the bomb. But as cops are intercepting the messages of unseen gang, they can’t directly send the number. So they have created a new way to represent a number in which

A=1
B=5
C=10
D=50
E=100
F=500
G=1000

Different numbers can be represented by the combination of this symbol.

For example
AAA=3
AC=9
CB=15

The gang member has sent the number using this system but the leader is confused by reading the messages because there are multiple ways to represent a single number.

For example sixteen can be represented by

AAAAAAAAAAAAAAAA
BAAAAAAAAAAA
BBAAAAAA
CAAAAAA
BBBA
CBA

Leader wants your help to convert every message into most efficient equivalent message. So that he can easily understand the message.

Note:-Most efficient equivalent message is the message which has same numerical value and has least number of symbols. In above example CBA is considered as most efficient message because it has the least number of symbols.

Input
The first line denotes T, the number of test cases.
The next T line represents T different messages of length L.

Output
For every message print the required message.

Constraints
0<=T<=100
1<=L<=20