ICCSECRET - Secret Key

no tags 

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

hide comments
Robert Lewon: 2023-09-18 13:20:37

This problem is once again available for solving!

Simes: 2020-09-24 16:16:03

Still no Submit button. It's been missing since 2016, can't somebody enable it?

susiconfusi: 2016-12-15 09:42:11

There seems to be no submit button.

Aleksandar Kostadinov: 2016-11-29 11:01:58

Enable submission or hide your problem.

levim: 2016-11-12 20:22:05

@umsh1ume Submission is giving "This problem can't be tested yet! "


Added by:Umesh Malhotra
Date:2016-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY