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: UNKNOWN_DIFFICULTY

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))


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


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))


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))


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)


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


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)


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)