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

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    S = input()
    n = len(S)
    a = n - S.count('a')
    print(2 ** n - 2 ** a)

for _ in range(int(input())):
    s=input()
    n=len(s)
    c=s.count('a')
    l=n-c
    print(pow(2,n)-pow(2,l))



for _ in range(int(input())):
    s=input()
    n=len(s)
    c=s.count('a')
    l=n-c
    print(pow(2,n)-pow(2,l))



try:
    t = int(input())
    for _ in range(t):
        s = input()
        acount = 0
        for i in s:
            if i == "a":
                acount+=1
        p = len(s) - acount
        base = 2**(acount) - 1
        print(base * 2**(p))
except:
    pass

# cook your dish here
t=int(input())
for _ in range(t):
    stringa=input()
    a=0
    counter=0
    for char in stringa:
        if char=='a':
            a+=1 
    print(2**(len(stringa)-a)*(2**a-1))


# cook your dish here
# code by RAJ BHAVSAR
import sys
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_list(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()
def get_int(): return int(sys.stdin.readline().strip())
def get_print_int(x): sys.stdout.write(str(x) + '\n')
def get_print(x): sys.stdout.write(x + '\n')

def solve():
	for _ in range(get_int()):
		s = get_string()
		n = len(s)
		count = 0
		for i in s:
			if(i == 'a'):
				count += 1
		get_print_int((2**n - 1) - (2**(n-count) - 1))
solve()

n=int(input())
for _ in range(n):
    c=0
    s=input()
    for i in s:
        if i=='a':
            c+= 1 
    print((2**len(s)-2**(len(s)-c)))# cook your dish here


# def count(a, b): 
# 	m = len(a);n = 1
# 	lookup = [[0] * (n + 1) for i in range(m + 1)] 
# 	for i in range(n+1): lookup[0][i] = 0
# 	for i in range(m + 1): lookup[i][0] = 1
# 	for i in range(1, m + 1): 
# 		for j in range(1, n + 1): 
# 			if a[i - 1] == b[j - 1]: lookup[i][j] = lookup[i - 1][j - 1] + lookup[i - 1][j]
# 			else: lookup[i][j] = lookup[i - 1][j] 
# 	return lookup[m][n]
# for _ in range(int(input())):
# 	a = input()
# 	b = "a"
# 	print(count(a, b)) #this just counts the number of times a string occurs, nut the subsequences
#>>> if there are only a's, then answer is (2**len) - 1
#>>> if there are len - 1 a's and one diff, then answer is (2**len) - 2
#>>> if there are len - 1 diff's and one a, then answer is 2**(len - 1)
#>>> if there are all diff, then answer is 0
#>>> 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)
#>>> wait a minute...2**len - 2**(len/2) this works for inequalities also (?)
for _ in range(int(input())):
	a = input();count = 0
	for i in a:
		if(i != "a"): count += 1
	print(2**len(a) - 2**count)

from math import factorial as fact
from itertools import combinations
for _ in range(int(input())):
    a=input()
    if "a" not in a:
        print(0)
        continue
    ct=a.count("a")
    ct="a"*ct
    a=a.replace("a","")
    count=0
    for i in range(1,len(a)+1):
        count+=(fact(len(a))/(fact(i)*(fact(len(a)-i))))
    ctcount=0
    for i in range(1,len(ct)+1):
        ctcount+=len(list(combinations(ct,i)))
    print(int(count)*ctcount+ctcount)

# cook your dish here
def power(a,b):
	if(b==0):
		return 1
	if(b==1):
		return a
	if(b%2==1):
		return (power(a,b-1)*a)
	x=power(a,b/2)
	return (x*x)
t=int(input())
while(t>0):
    s=input()
    b=s.count("a")
    n=len(s)
    if(b==0):
        print(0)
    else:
        c=n-b
        print(power(2,n)-power(2,c))
    t-=1
    



# cook your dish here
n = int(input())
for i in range(n):
    w = input()
    l = len(w)
    s = 0
    a = 0
    for i in w:
        if i == 'a':
            a += 1
            s += 2**(l-a)
    print(s)

# cook your dish here
for u in range(int(input())):
    s=input()
    n=len(s)
    x=s.count('a')
    z=n-x
    s=2**x-1
    c=2**z
    print(s*c)