VARIATIONSTM - Variations

no tags 

The internet is not as safe as it was in the past. One evidence of it is the increase in the number of hacker attacks. To worsen, when a hacker steals a password from a user in a specific site, he has access to all the other accounts of this user in other sites, because most of the users nowadays use the same password in all sites.

One of the proposed solutions to this problem is to use different passwords for each site, or even different variations of the same password. For example, to vary the password “potato”, it's possible to use the password “pOtaTo”, “P0tat0”, “pot4TO”, etc. In other words, for each character of the alphabet, it's possible to make a variation changing the case of the character (lower case or upper case). Moreover, to increase the total number of variations, for the characters A, E, I, O and S it's possible to use the numbers 4, 3, 1, 0 and 5, respectively.

Your friend needs to increase the number of variations of his password, and asked for your help. Given the password that he chose, find out the number of different variations that it's possible to build.

Input

The first line contains an integer T, indicating the number of test cases to follow.

Each test case contains a sequence of characters S, indicating your friend's password. For each password, there will be at least 1 and at most 16 characters, which can be any of the 26 letters of the alphabet, lower or upper case.

Output

For each test case print one line containing one integer, indicating the number of different variations that is possible to build with the given password, including itself.

Example

Input:
4
bB
ab
Ee
bAtatA Output: 4
6
9
216

hide comments
ANIKET: 2015-09-22 07:46:29

Nice question

RIVU DAS: 2015-09-21 17:08:32

Tutorial!

coppercastle: 2015-09-19 07:27:16

Tutorial problem :)

ravi12345: 2015-09-18 21:04:44

very easy


Added by:noname
Date:2015-09-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:By Cristhian Bonilha, UTFPR BR Brazil