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) (pattern consists 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