You are working in security cell of your Institute Computer Center (ICC) and want to generate a secret key following a pattern. The pattern consists of the characters 'A' and 'B' where 'A' means increasing and 'B' means decreasing. Generate the secret key which is the minimum number encoded following that pattern.

Digits 1-9 in the key and digits can not repeat.

Input

Input starts with an integer T denoting the number of test cases.

T lines follows containing pattern string (length <= 8) consisting of 'A' and 'B' only.

Output

For every test case, output the minimum number denoting that pattern.

Example

Input:
2
AABBA
BBBA
Output:
125436
43215