You are given a string $s$, consisting only of Latin letters 'a', and a string $t$, consisting of lowercase Latin letters.

In one move, you can replace any letter 'a' in the string $s$ with a string $t$. Note that after the replacement string $s$ might contain letters other than 'a'.

You can perform an arbitrary number of moves (including zero). How many different strings can you obtain? Print the number, or report that it is infinitely large.

Two strings are considered different if they have different length, or they differ at some index.


-----Input-----

The first line contains a single integer $q$ ($1 \le q \le 10^4$) — the number of testcases.

The first line of each testcase contains a non-empty string $s$, consisting only of Latin letters 'a'. The length of $s$ doesn't exceed $50$.

The second line contains a non-empty string $t$, consisting of lowercase Latin letters. The length of $t$ doesn't exceed $50$.


-----Output-----

For each testcase, print the number of different strings $s$ that can be obtained after an arbitrary amount of moves (including zero). If the number is infinitely large, print -1. Otherwise, print the number.


-----Examples-----

Input
3
aaaa
a
aa
abc
a
b
Output
1
-1
2


-----Note-----

In the first example, you can replace any letter 'a' with the string "a", but that won't change the string. So no matter how many moves you make, you can't obtain a string other than the initial one.

In the second example, you can replace the second letter 'a' with "abc". String $s$ becomes equal to "aabc". Then the second letter 'a' again. String $s$ becomes equal to "aabcbc". And so on, generating infinitely many different strings.

In the third example, you can either leave string $s$ as is, performing zero moves, or replace the only 'a' with "b". String $s$ becomes equal to "b", so you can't perform more moves on it.

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Combinatorics

Implementation


Solutions:
input = open(0).readline
for _ in range(int(input())):
	a = input().strip()
	t = input().strip()
	if t == 'a':
		print(1)
	elif 'a' in t:
		print(-1)
	else:
		print(2 ** len(a))


import sys
input = iter(sys.stdin.read().splitlines()).__next__

def solve(S, T):
	if 'a' in T:
		return 1 if len(T) == 1 else -1
	return 2 ** S.count('a')
TC = int(input())
for tc in range(TC):
	S = input().strip()
	T = input().strip()
	res = solve(S, T)
	print(res)


import sys
testcase = int(sys.stdin.readline().strip())
for i in range(testcase):
	dic = {}
	s = sys.stdin.readline().strip()
	t = sys.stdin.readline().strip()
	dic[s] = 1
	if t == 'a':
		print(1)
		continue
	elif 'a' in t:
		print(-1)
		continue
	else:
		print(2 ** s.count('a'))


from sys import stdin

def read_int():
	return int(stdin.readline())

def read_list(_type=int):
	return list(map(_type, stdin.readline().split()))

def read_tuple():
	return stdin.readline().split()

def read_string():
	return stdin.readline().rstrip('\r\n')
for _ in range(read_int()):
	s = read_string()
	t = read_string()
	if t == 'a':
		print(1)
	elif t.count('a'):
		print(-1)
	else:
		print(2 ** len(s))


import sys

def solve():
	s = sys.stdin.readline().strip()
	t = sys.stdin.readline().strip()
	if t == 'a':
		print(1)
	elif t.find('a') != -1:
		print(-1)
	else:
		print(2 ** len(s))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		s = len(rs())
		t = rs()
		if 'a' in t:
			if len(t) == 1:
				print(1)
			else:
				print(-1)
		else:
			print(2 ** s)
main()


import sys
input = lambda : sys.stdin.readline().strip()
a = int(input())
for i in range(a):
	b = input()
	c = input()
	if c == 'a':
		print(1)
	elif 'a' in c:
		print(-1)
	else:
		print(2 ** len(b))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input()[:-1]
	t = input()[:-1]
	if t == 'a':
		print(1)
	elif 'a' in t:
		print(-1)
	else:
		print(2 ** len(s))


import sys
q = int(sys.stdin.readline().strip())
for _ in range(q):
	s = sys.stdin.readline().strip()
	t = sys.stdin.readline().strip()
	if len(t) > 1 and 'a' in t:
		print(-1)
	elif t == 'a':
		print(1)
	else:
		n = len(s)
		print(int(1 << n))


import sys

def factorial(total, index):
	if index == 0:
		return total
	else:
		return factorial(total * index, index - 1)

def fn(s, t):
	if not s:
		return 0
	if not t or t == 'a':
		return 1
	if 'a' in t:
		return -1
	return 2 ** len(s)
input = sys.stdin.readlines()
for i in range(int(input[0].strip('\n'))):
	(s, t) = (input[2 * i + 1].strip('\n'), input[2 * i + 2].strip('\n'))
	out = fn(s, t)
	print(out)


out = []
for _ in range(int(input())):
	s = input()
	t = input()
	if t == 'a':
		out.append(1)
		continue
	if 'a' in t:
		out.append(-1)
		continue
	out.append(2 ** len(s))
for i in out:
	print(i)


import sys
input = sys.stdin.readline

def sol(s, t):
	if t == 'a':
		return 1
	if t.find('a') >= 0:
		return -1
	return 2 ** len(s)
T = int(input())
for _ in range(T):
	s = input().strip()
	t = input().strip()
	ret = sol(s, t)
	print(ret)


num_tests = int(input(''))
problems = []
for i in range(0, num_tests):
	s = input('')
	t = input('')
	problems.append((s, t))
for (s, t) in problems:
	if 'a' in t and len(t) > 1:
		print(-1)
		continue
	elif t == 'a':
		print('1')
		continue
	else:
		print(2 ** len(s))


t = int(input())
res = []
for i in range(t):
	base = input()
	new = input()
	if new == 'a':
		res.append(1)
	elif new.find('a') != -1:
		res.append(-1)
	else:
		n = base.count('a')
		res.append(2 ** n)
for i in res:
	print(i)


import math as m
i = input()
inp = []
for a in range(0, int(i)):
	inp += [[input(), input()]]
for i in inp:
	s = i[0]
	t = i[1]
	n = len(s)
	if 'a' in t:
		if len(t) == 1:
			print(1)
		else:
			print(-1)
	else:
		print(2 ** n)


CHAR = 'a'
all_obtainable = []
for _ in range(int(input())):
	init = input()
	replace = input()
	if CHAR in replace:
		all_obtainable.append(1 if len(replace) == 1 else -1)
	else:
		all_obtainable.append(2 ** init.count(CHAR))
print('\n'.join((str(o) for o in all_obtainable)))


q = int(input())
result = []
for i in range(q):
	s = input()
	t = input()
	if t == 'a':
		result.append(1)
	elif len(t) >= 2 and 'a' in t:
		result.append(-1)
	else:
		result.append(2 ** len(s))
for x in result:
	print(x)


t = int(input())
st = []
pt = []
for _ in range(t):
	st += [input()]
	pt += [input()]
for i in range(t):
	s = st[i]
	p = pt[i]
	l = []
	if 'a' in p and p != 'a':
		print(-1)
	elif p == 'a':
		print(1)
	else:
		print(2 ** len(s))


import sys
input = sys.stdin.readline

def solve():
	a = input().strip()
	b = input().strip()
	if b == 'a':
		print(1)
		return
	if 'a' in b:
		print(-1)
		return
	print(1 << a.count('a'))
T = int(input())
for _ in range(T):
	solve()


def Solve():
	(ss, rs) = ([], [])
	for t in range(int(input())):
		ss.append(input())
		rs.append(input())
	for (s, r) in zip(ss, rs):
		if 'a' in s:
			if r == 'a':
				print(1)
			elif 'a' in r:
				print(-1)
			else:
				print(2 ** len(s))
		else:
			print(0)
Solve()


n = int(input())
vet = []
while n > 0:
	n -= 1
	a = input()
	b = input()
	if b == 'a':
		vet.append(1)
	elif 'a' in b and len(b) > 1:
		vet.append(-1)
	else:
		vet.append(2 ** len(a))
print(*vet, sep='\n')


from functools import lru_cache
import sys
import threading

def input():
	return sys.stdin.readline().rstrip('\r\n')

def main():
	q = int(input())
	for _ in range(q):
		s = input()
		t = input()
		if t != 'a' and 'a' in t:
			print(-1)
			continue
		if t == 'a':
			print(1)
			continue
		print(2 ** len(s))
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


def value(string1, string2):
	count = string2.count('a')
	if count == 0:
		return 2 ** len(string1)
	elif count >= 1:
		if len(string2) == 1:
			return 1
		else:
			return -1

def main():
	n = int(input())
	data = []
	for i in range(n):
		string1 = input()
		string2 = input()
		data.append([string1, string2])
	for strings in data:
		print(value(strings[0], strings[1]))
main()


k = int(input())
p = [0] * k
for i in range(k):
	s = input()
	t = input()
	if len(t) > 1 and t.find('a') != -1:
		p[i] = -1
	elif len(t) == 1 and t[0] == 'a':
		p[i] = 1
	else:
		p[i] = 2 ** len(s)
for j in range(k):
	print(p[j])


n = input()
test_cases_a = []
test_cases_b = []
for i in range(0, int(n)):
	test_cases_a.append(input())
	test_cases_b.append(input())
for i in range(0, len(test_cases_b)):
	length_b = len(test_cases_b[i])
	length_a = len(test_cases_a[i])
	if length_b == 1:
		if test_cases_b[i] == 'a':
			print('1')
		else:
			print(2 ** length_a)
	elif 'a' in test_cases_b[i]:
		print(-1)
	else:
		print(2 ** length_a)


t = int(input())
ans = []
for i in range(t):
	q = input()
	s = input()
	if s.count('a') == 0:
		ans.append(2 ** len(q))
	elif s.count('a') != len(s):
		ans.append(-1)
	elif len(s) != 1:
		ans.append(-1)
	else:
		ans.append(1)
for elem in ans:
	print(elem)


q = int(input())
ans = []
for _ in range(q):
	s = input()
	t = input()
	if t == 'a':
		ans.append(1)
	elif len(t) == 1:
		ans.append(2 ** len(s))
	elif 'a' in t:
		ans.append(-1)
	else:
		ans.append(2 ** len(s))
for i in ans:
	print(i)


n_test_cases = int(input())
results = []
for _ in range(n_test_cases):
	s = input()
	t = input()
	if t == 'a':
		results.append(1)
		continue
	a_freq = t.count('a')
	if a_freq >= 1:
		results.append(-1)
	elif len(s) == 1:
		results.append(2)
	else:
		results.append(pow(2, len(s)))
for result in results:
	print(result)


def input_strings():
	input_data = []
	number_cases = int(input())
	for case in range(number_cases):
		input_data.append([input(), input()])
	return input_data
data = input_strings()
for case in data:
	s = case[0]
	t = case[1]
	if t == 'a':
		print('1')
		continue
	if 'a' in t:
		print('-1')
		continue
	print(2 ** len(s))


import sys

def countStringsPossible(s, t):
	if set(s) == set(t) and len(t) == 1:
		return 1
	elif len(s) == 1 and len(t) == 1:
		return 2
	l = len(s)
	if 'a' not in t:
		return 2 ** l
	else:
		return -1
tc = int(sys.stdin.readline())
for i in range(tc):
	s = sys.stdin.readline().strip()
	t = sys.stdin.readline().strip()
	print(countStringsPossible(s, t))


n = int(input())
ans = []
for i in range(n):
	s = input()
	t = input()
	len_s = len(s)
	len_t = int(len(t))
	if t.count('a') == 0:
		ans.append(2 ** len_s)
	elif t.count('a') == len_t and len_t == 1:
		ans.append(1)
	else:
		ans.append(-1)
for i in range(n):
	print(ans[i])


count = int(input())
first = []
second = []
for i in range(0, count):
	first.append(input())
	second.append(input())
for i in range(0, count):
	if len(second[i]) == 1:
		if second[i] == 'a':
			print('1')
		else:
			print(2 ** len(first[i]))
	elif second[i].find('a') == -1:
		print(2 ** len(first[i]))
	else:
		print('-1')


def fn():
	a = input()
	b = input()
	m = 0
	for i in b:
		if i == 'a':
			m += 1
	if m != 0 and len(b) > 1:
		return '-1'
	if m == 0:
		return str(2 ** len(a))
	if b == 'a':
		return '1'
a = int(input())
k = []
for j in range(a):
	k.append(fn())
for h in k:
	print(h)


a = int(input())
sp = []
for i in range(a):
	b = input()
	c = input()
	if b.count('a') == len(b) and c == 'a':
		sp.append(1)
	elif 'a' in c:
		sp.append(-1)
	else:
		sp.append(2 ** b.count('a'))
for i in sp:
	print(i)


import sys
msg = sys.stdin.readlines()
for i in range(int(msg[0])):
	p = True
	lst = msg[2 * i + 1].strip('\n')
	lst2 = msg[2 * i + 2].strip('\n')
	a = False
	if len(lst2) > 1:
		other = True
	else:
		other = False
	for j in lst2:
		if j == 'a':
			a = True
		if a and other:
			print(-1)
			p = False
			break
	if p:
		if 'a' in lst2:
			print(1)
		else:
			print(2 ** len(lst))


for _ in ' ' * int(input()):
	(a, b) = (input(), input())
	if 'a' in b:
		if len(b) == 1:
			print(1)
		else:
			print(-1)
	else:
		print(2 ** len(a))


def solution():
	(s, t) = (input(), input())
	if 'a' not in t:
		return 2 ** len(s)
	if t == 'a':
		return 1
	return -1
t = int(input())
for _ in range(t):
	print(solution())


n = int(input())
for i in range(n):
	a = input()
	b = input()
	if b == 'a':
		print(1)
	elif 'a' in b:
		print(-1)
	else:
		print(2 ** len(a))


x = input
for i in range(int(x())):
	a = x()
	b = x()
	if b == 'a':
		print(1)
	elif 'a' in b:
		print(-1)
	else:
		print(2 ** a.count('a'))


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def main():
	for _ in range(int(input())):
		s = input()
		t = input()
		if t == 'a':
			print(1)
		elif 'a' in t:
			print(-1)
		else:
			n = len(s)
			print(1 << n)
main()


for i in range(int(input())):
	s = input()
	t = input()
	if t == 'a':
		print(1)
	elif 'a' in t:
		print(-1)
	else:
		print(pow(2, len(s)))


I = input
for _ in [0] * int(I()):
	print((1 << len(I()), 1 - 2 * ((t := I()) > 'a'))['a' in t])


for _ in range(int(input())):
	s = input()
	t = input()
	if t == 'a':
		print(1)
		continue
	if 'a' in t:
		print(-1)
		continue
	print(2 ** len(s))


for _ in range(int(input())):
	s = input()
	t = input()
	if t == 'a':
		print(1)
	elif len(t) == 1 or 'a' not in t:
		print(2 << len(s) - 1)
	else:
		print(-1)


q = int(input())
for _ in range(q):
	s = input()
	t = input()
	if 'a' in t and len(t) > 1:
		print(-1)
	elif t == 'a':
		print(1)
	else:
		print(2 ** len(s))


for t in range(int(input())):
	s = input()
	s1 = input()
	c = s1.count('a')
	if s1 == 'a':
		print(1)
		continue
	if c > 0:
		print(-1)
		continue
	n = len(s)
	print(2 ** n)


for _ in range(int(input())):
	s = input()
	t = input()
	if t == 'a':
		print(1)
	elif t.count('a') > 0:
		print(-1)
	else:
		print(2 ** len(s))


def main():
	t = int(input())
	for _ in range(t):
		s = input()
		k = input()
		if 'a' in k and (k.count('a') != len(k) or len(k) > 1):
			print(-1)
		elif 'a' in k and k.count('a') == len(k):
			print(1)
		else:
			print(2 ** len(s))
main()


for _ in range(int(input())):
	a = input()
	b = input()
	if b == 'a':
		print(1)
		continue
	if 'a' in b:
		print(-1)
		continue
	print(2 ** len(a))


def _i():
	return int(input())

def _f():
	return float(input())

def _iln():
	ln = input().split(' ')
	return [int(i) for i in ln]

def _ln():
	return input().split(' ')

def solve(tt):
	s = input()
	t = input()
	if t == 'a':
		print(1)
		return
	if 'a' in t:
		print(-1)
		return
	print(2 ** s.count('a'))
t = _i()
for i in range(1, t + 1):
	solve(i)


cnt = int(input())
i = 1
while i <= cnt:
	s = input()
	t = input()
	if t == 'a':
		print(1)
	elif 'a' in t:
		print(-1)
	else:
		print(pow(2, len(s)))
	i += 1


import math
t = int(input())
for _ in range(t):
	s = input()
	t = input()
	if 'a' in t and t != 'a':
		print(-1)
		continue
	if t == 'a':
		print(1)
		continue
	print(2 ** len(s))


t = int(input())
for i in range(t):
	a = input()
	b = input()
	if 'a' in b and len(b) > 1:
		print(-1)
	elif b == 'a':
		print(1)
	else:
		l = len(a)
		print(2 ** l)


t = int(input())
for i in range(t):
	s = str(input())
	t = str(input())
	x = 0
	if t == 'a':
		x = 1
	elif 'a' in t:
		x = -1
	else:
		x = 2 ** len(s)
	print(x)


t = int(input())
for i in range(t):
	a = input()
	b = input()
	if len(b) > 1:
		if b.count('a') > 0:
			print(-1)
		else:
			print(2 ** len(a))
	elif b == 'a':
		print(1)
	else:
		print(2 ** len(a))


n = int(input())
for i in range(n):
	s = input()
	t = input()
	if len(t) > 1 and 'a' in t:
		print('-1')
	else:
		print(1 if t == 'a' else 2 ** len(s))


for _ in range(int(input())):

	def fun(s, t):
		if t == 'a':
			return 1
		if 'a' in t:
			return -1
		return 2 ** len(s)
	s = input()
	t = input()
	print(fun(s, t))


def solve_one():
	first_line = input()
	second_line = input()
	second_line_letters = set(second_line)
	if second_line == 'a':
		return 1
	if 'a' in second_line_letters:
		return -1
	return 2 ** len(first_line)

def solve_task():
	t = int(input())
	anss = []
	for _ in range(t):
		anss.append(solve_one())
	for ans in anss:
		print(ans)
solve_task()


n = int(input())
for i in range(n):
	s = input()
	t = input()
	if t == 'a':
		print(1)
	elif 'a' in t:
		print(-1)
	elif not 'a' in t:
		print(2 ** len(s))


t = input()
for i in range(int(t)):
	a = input()
	s = input()
	cnt = s.count('a')
	if cnt == 0:
		print(pow(2, len(a)))
	elif cnt == 1 and len(s) == 1:
		print(1)
	else:
		print(-1)


T = int(input())
for _ in range(T):
	s = input()
	t = input()
	if t == 'a':
		print(1)
	elif 'a' in t:
		print(-1)
	else:
		print(1 << len(s))


t = int(input())

def factorial(n):
	if n < 0:
		return 0
	elif n == 0 or n == 1:
		return 1
	else:
		fact = 1
		while n > 1:
			fact *= n
			n -= 1
		return fact
for _ in range(t):
	s = input()
	t = input()
	lns = len(s)
	if 'a' in t:
		if len(t) == 1:
			print('1')
		else:
			print('-1')
	else:
		print(2 ** lns)


nq = int(input())
for i in range(nq):
	ms = input()
	s = input()
	c = s.count('a')
	if c > 0 and len(s) != 1:
		print(-1)
	elif c > 0:
		print(1)
	else:
		print(2 ** len(ms))


t = int(input())
for i in range(t):
	s1 = input()
	s2 = input()
	if s2 == 'a':
		print(1)
	elif 'a' in s2:
		print(-1)
	else:
		print(2 ** len(s1))


def main():
	o = 0
	s = input()
	t = input()
	if 'a' in t:
		if len(t) > 1:
			return -1
		else:
			return 1
	return int(2 ** len(s))
	return o
t = int(input())
for _ in range(t):
	print(main())


tc = int(input())
for case in range(tc):
	s = input()
	t = input()
	sa = len(s)
	if t == 'a':
		print(1)
	elif 'a' in t:
		print(-1)
	else:
		print(1 << len(s))


for T in range(int(input())):
	s = input()
	t = input()
	if 'a' in t:
		if len(t) == 1:
			print(1)
		else:
			print(-1)
	else:
		print(2 ** len(s))


for _ in range(int(input())):
	a = input()
	b = input()
	if b == 'a':
		print('1')
	elif 'a' in b:
		print('-1')
	else:
		print(pow(2, len(a)))


t = int(input())
while t:
	t -= 1
	s = input()
	x = input()
	if x == 'a':
		print(1)
	elif 'a' in x:
		print(-1)
	else:
		print(2 ** len(s))


def main():
	test = int(input())
	for LOVE in range(test):
		s = input()
		t = input()
		n = len(s)
		if 'a' in t:
			if len(t) == 1:
				print(1)
			else:
				print(-1)
		else:
			print(1 << n)
main()


t = int(input())
for _ in range(t):
	s = input()
	s2 = input()
	if s2 == 'a':
		print(1)
	elif 'a' in s2:
		print(-1)
	else:
		print(2 ** s.count('a'))