You came across this story while reading a book. Long a ago when the modern entertainment systems did not exist people used to go to watch plays in theaters, where people would perform live in front of an audience. There was a beautiful actress who had a disability she could not pronounce the character $'r'$. To win her favours which many have been denied in past, you decide to write a whole play without the character $'r'$. Now you have to get the script reviewed by the editor before presenting it to her.
The editor was flattered by the script and agreed to you to proceed. The editor will edit the script in this way to suit her style. For each word replace it with a sub-sequence of itself such that it contains the character 'a'. 
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements Wikipedia 
Now given a script with $N$ words, for each word in the script you wish to know the number of subsequences with which it can be replaced. 

-----Input:-----
- First-line will contain $N$, the number of words in the script. Then next $N$ line with one test case each. 
- Each test case contains a single word $W_i$

-----Output:-----
For each test case, output in a single line number of subsequences with which it can be replaced. 

-----Constraints-----
- $1 \leq N \leq 1000$
- $1 \leq$ length of $W_i$  $\leq 20$
- $W_i$  on contains lowercase english alphabets and does not have the character 'r'

-----Sample Input 1:-----
2
abc
aba

-----Sample Output 1:-----
4
6

-----EXPLANATION:-----
This subsequences with which $abc$ can be replaed : ${a,ab,ac,abc}$. 
This subsequences with which $aba$ can be replaed : ${a,ab,aba,a,ba,a}$. 

-----Sample Input 2:-----
3
abcde
abcdea
xyz

-----Sample Output 2:-----
16
48
0

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# def count(a, b): \n# \tm = len(a);n = 1\n# \tlookup = [[0] * (n + 1) for i in range(m + 1)] \n# \tfor i in range(n+1): lookup[0][i] = 0\n# \tfor i in range(m + 1): lookup[i][0] = 1\n# \tfor i in range(1, m + 1): \n# \t\tfor j in range(1, n + 1): \n# \t\t\tif a[i - 1] == b[j - 1]: lookup[i][j] = lookup[i - 1][j - 1] + lookup[i - 1][j]\n# \t\t\telse: lookup[i][j] = lookup[i - 1][j] \n# \treturn lookup[m][n]\n# for _ in range(int(input())):\n# \ta = input()\n# \tb = "a"\n# \tprint(count(a, b)) #this just counts the number of times a string occurs, nut the subsequences\n#>>> if there are only a\'s, then answer is (2**len) - 1\n#>>> if there are len - 1 a\'s and one diff, then answer is (2**len) - 2\n#>>> if there are len - 1 diff\'s and one a, then answer is 2**(len - 1)\n#>>> if there are all diff, then answer is 0\n#>>> there has to be a direct relation somewhere...gottit..if there are equal a\'s and diffs, then answer is 2**len - 2**(len/2)\n#>>> wait a minute...2**len - 2**(len/2) this works for inequalities also (?)\nfor _ in range(int(input())):\n\ta = input();count = 0\n\tfor i in a:\n\t\tif(i != "a"): count += 1\n\tprint(2**len(a) - 2**count)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12907