Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

Two players (let's call them A and B) are playing a game on a row of cells. A cell may contain the character 'A', contain the character 'B' or be empty. Each character may only be moved from a cell $c_{i}$ to a cell $c_{f}$ if cell $c_{f}$ and all cells between $c_{i}$ and $c_{f}$ are currently empty. The leftmost (first) character may only be moved to the right, the second character may only be moved to the left, the next character to the right, and so on. Each character may be moved any number of times, including zero.

The players alternate turns; player A starts. On each turn, the current player must choose a cell containing their own character ('A' for player A, 'B' for player B) and move it to a different cell. This cell may be chosen arbitrarily as long as all rules described above are satisfied. The first player that cannot move a character loses.

Note that each character is always moved in a fixed direction, so the game is finite. Determine the winner of the game if both players play optimally.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single string $s$ describing the initial state of the row of cells. Each character of $s$ is either 'A', 'B' or '.', denoting a cell containing 'A', a cell containing 'B' or an empty cell respectively.

------  Output ------
For each test case, print a single line containing the string "A" if player A wins or "B" if player B wins.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ |s| ≤ 10^{5}$
the sum of $|s|$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
3
A.B
A..B
A..B.A..B
----- Sample Output 1 ------ 
A
A
B
----- explanation 1 ------ 
Example case 1: Player A can move the first character 'A' one cell to the right. Now, player B cannot move and loses.

Example case 2: Player A can move the first character two cells to the right (to the cell adjacent to 'B'). Again, player B cannot move and loses.

Difficulty: VERY_HARD
Tags: Game theory

Starter code:

Solutions:
for _ in range(int(input())):
	s = input()
	string = ''
	pair = -1
	(Amoves, Bmoves, count) = (0, 0, 0)
	nim = [0, 0]
	for i in s:
		if pair == -1:
			if i == '.':
				continue
			string = i
			pair = 0
		elif pair == 0:
			if i == '.':
				count += 1
			elif string == i:
				if string == 'A':
					Amoves += count
				else:
					Bmoves += count
				pair = 1
				count = 0
			else:
				nim.append(count)
				count = 0
				pair = 1
		elif pair == 1:
			if i != '.':
				string = i
				pair = 0
	if pair == 0:
		if string == 'A':
			Amoves += count
		else:
			Bmoves += count
	if Amoves > Bmoves:
		print('A')
	elif Bmoves > Amoves:
		print('B')
	else:
		x = nim[0]
		for i in nim[1:]:
			x = x ^ i
		if x == 0:
			print('B')
		else:
			print('A')


from functools import reduce
T = int(input())
for t in range(T):
	s = input()
	N = len(s)
	ABcnts = []
	HP = {}
	HP['A'] = 0
	HP['B'] = 0
	firstChar = None
	SeconChar = None
	cnt = 0
	outside = True
	for i in range(N):
		if not outside and i == N - 1 and (s[i] == '.'):
			cnt += 1
			HP[firstChar] += cnt
			break
		if outside and s[i] != '.':
			outside = False
			firstChar = s[i]
		elif not outside and s[i] == '.':
			cnt += 1
		elif not outside and s[i] != '.':
			SeconChar = s[i]
			if firstChar != SeconChar:
				ABcnts.append(cnt)
				cnt = 0
			else:
				HP[firstChar] += cnt
				cnt = 0
			outside = True
		elif outside and s[i] == '.':
			continue
	xor = lambda a, b: a ^ b
	if len(ABcnts) != 0:
		nimA = reduce(xor, ABcnts)
		if nimA == 0:
			if HP['A'] <= HP['B']:
				print('B')
			elif HP['A'] > HP['B']:
				print('A')
		elif HP['A'] < HP['B']:
			print('B')
		elif HP['A'] >= HP['B']:
			print('A')
	elif HP['A'] <= HP['B']:
		print('B')
	elif HP['A'] > HP['B']:
		print('A')


inp = int(input())
while inp:
	inp -= 1
	data = input()
	turn = True
	prev = 'C'
	prevPos = 0
	currPos = 0
	count = dict()
	count['A'] = 0
	count['B'] = 0
	txor = 0
	for char in data:
		if char != '.':
			turn ^= True
			if turn:
				if prev == char:
					count[prev] += currPos - prevPos - 1
				else:
					txor ^= currPos - prevPos - 1
			else:
				prevPos = currPos
				prev = char
		currPos += 1
	if turn == False and prev != 'C':
		count[prev] += currPos - prevPos - 1
	if count['A'] + int(txor > 0) > count['B']:
		print('A')
	else:
		print('B')


T = int(input())
for _ in range(T):
	s = input()
	moveAB = moveA = moveB = pos = nim = 0
	(i, found) = (0, False)
	while i < len(s):
		if s[i] in ['A', 'B'] and i + 1 < len(s) and (s[i + 1] == '.'):
			for j in range(i + 1, len(s)):
				if s[j] in ['A', 'B']:
					found = True
					pos = j
					if s[j] == s[i]:
						if s[j] == 'A':
							moveA += j - i - 1
						else:
							moveB += j - i - 1
					else:
						nim ^= j - i - 1
					break
			if found:
				i = pos + 1
				found = False
				continue
			else:
				if s[i] == 'A':
					moveA += len(s) - i - 1
				else:
					moveB += len(s) - i - 1
				break
		elif s[i] in ['A', 'B'] and i + 1 < len(s) and (s[i + 1] in ['A', 'B']):
			i += 2
		else:
			i += 1
	if moveA > moveB:
		print('A')
	elif moveB > moveA:
		print('B')
	elif nim != 0:
		print('A')
	else:
		print('B')


t = int(input())
while t > 0:
	s = input()
	d = []
	c = []
	flag = 0
	ls = len(s)
	si = 0
	for i in range(ls):
		if s[i] != '.':
			if flag != 1:
				si = i
				flag = 1
			else:
				flag = 0
				ee = i
				d.append(s[si:ee + 1])
		elif flag == 1 and i == ls - 1:
			d.append(s[si:ls])
	mb = 0
	ma = 0
	e = []
	for i in range(len(d)):
		if d[i][0] == 'A' and d[i][-1] == 'A':
			ma += len(d[i]) - 2
		elif d[i][0] == 'B' and d[i][-1] == 'B':
			mb += len(d[i]) - 2
		elif d[i][-1] == '.':
			if d[i][0] == 'A':
				ma += len(d[i]) - 1
			elif d[i][0] == 'B':
				mb += len(d[i]) - 1
		else:
			e.append(len(d[i]) - 2)
	if mb == ma:
		ns = 0
		s = s[0]
		for i in range(len(e)):
			ns = ns ^ e[i]
		if ns != 0:
			print('A')
		else:
			print('B')
	elif mb > ma:
		print('B')
	else:
		print('A')
	t -= 1


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	a = [0, 0]
	b = 0
	i = 0
	while i < n:
		i = next((i for i in range(i, n) if s[i] != '.'), n)
		if i < n:
			(j, c) = next(((j, s[j]) for j in range(i + 1, n) if s[j] != '.'), (n, s[i]))
			l = j - i - 1
			if c == s[i]:
				a[c == 'B'] += l
			else:
				b ^= l
			i = j + 1
	print('BA'[a[0] + (b != 0) > a[1]])


t = int(input())
while t != 0:
	s1 = input()
	count = 0
	l1 = []
	for i in s1:
		if i == '.':
			count += 1
		else:
			l1.append(count)
			l1.append(i)
			count = 0
	if count != 0:
		l1.append(count)
	if l1[0] != 'A' or l1[0] != 'B':
		l1.pop(0)
	t = t - 1
	a_c = l1.count('A')
	b_c = l1.count('B')
	l_stacks = []
	res_a = 0
	res_b = 0
	if (a_c + b_c) % 2 == 0:
		for i in range(0, len(l1), 4):
			if l1[i] == l1[i + 2] == 'A':
				res_a += l1[i + 1]
			elif l1[i] == l1[i + 2] == 'B':
				res_b += l1[i + 1]
			elif l1[i] == 'A' and l1[i + 2] == 'B' or (l1[i] == 'B' and l1[i + 2] == 'A'):
				l_stacks.append(l1[i + 1])
	else:
		if l1[-1] == 'A' or l1[-1] == 'B':
			l1.pop(-1)
		elif l1[-2] == 'A':
			res_a += l1[-1]
			l1.pop(-2)
			l1.pop(-1)
		elif l1[-2] == 'B':
			res_b += l1[-1]
			l1.pop(-1)
			l1.pop(-1)
		for i in range(0, len(l1), 4):
			if l1[i] == l1[i + 2] == 'A':
				res_a += l1[i + 1]
			elif l1[i] == l1[i + 2] == 'B':
				res_b += l1[i + 1]
			elif l1[i] == 'A' and l1[i + 2] == 'B' or (l1[i] == 'B' and l1[i + 2] == 'A'):
				l_stacks.append(l1[i + 1])
	xor = 0
	for i in l_stacks:
		xor = xor ^ i
	if res_a > res_b:
		print('A')
	elif res_a < res_b:
		print('B')
	elif xor == 0:
		print('B')
	else:
		print('A')


def solve():
	gl = input()
	n = len(gl)
	prev = '.'
	pos = -1
	x = 0
	resa = 0
	resb = 0
	for i in range(n):
		if gl[i] != '.':
			if prev == '.':
				prev = gl[i]
				pos = i
			else:
				e = i - pos - 1
				if prev != gl[i]:
					x = x ^ e
				elif prev == 'A':
					resa += e
				else:
					resb += e
				prev = '.'
				pos = -1
	if prev != '.':
		if prev == 'A':
			resa += n - pos - 1
		else:
			resb += n - pos - 1
	if x > 0:
		resa += 1
	if resa > resb:
		print('A')
	else:
		print('B')

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def solve(S):
	A = B = 0
	nim = 0
	i = 0
	while i < len(S):
		if S[i] == '.':
			i += 1
			continue
		j = i + 1
		while j < len(S) and S[j] == '.':
			j += 1
		if j == len(S):
			if S[i] == 'A':
				A += j - i - 1
			else:
				B += j - i - 1
		else:
			if S[i] != S[j]:
				nim ^= j - i - 1
			if S[i] == S[j]:
				if S[i] == 'A':
					A += j - i - 1
				else:
					B += j - i - 1
		i = j + 1
	if A > B:
		return 'A'
	if B > A:
		return 'B'
	return 'A' if nim != 0 else 'B'
T = int(input())
for i in range(0, T):
	print(solve(input()))


tests = int(input())
for t in range(tests):
	s = input()
	if len(s) == 1:
		print('B')
	else:
		ind = 0
		while ind < len(s):
			e = s[ind]
			if e != '.':
				prev = e
				break
			ind += 1
		right = True
		counter = 0
		movesa = 0
		movesb = 0
		gap = 0
		for i in range(ind + 1, len(s)):
			e = s[i]
			if e == '.':
				gap += 1
				if i == len(s) - 1 and right:
					if prev == 'A':
						movesa += gap
					else:
						movesb += gap
				continue
			else:
				if right and gap > 0:
					if e != prev:
						counter ^= gap
					elif e == 'A':
						movesa += gap
					else:
						movesb += gap
				prev = e
				gap = 0
				right = not right
		if movesa > movesb:
			print('A')
		elif movesa < movesb:
			print('B')
		elif counter == 0:
			print('B')
		else:
			print('A')


for _ in range(int(input())):
	s = input()
	n = len(s)
	odd = False
	a = []
	aw = 0
	for i in range(n):
		if s[i] != '.':
			a.append(i)
	n1 = len(a)
	if n1 % 2 != 0:
		odd = True
		n1 -= 1
	for i in range(0, n1 - 1, 2):
		if s[a[i]] != s[a[i + 1]] and a[i + 1] != a[i] + 1:
			aw ^= a[i + 1] - a[i] - 1
	if aw == 0:
		aw = 0
	else:
		aw = 1
	for i in range(0, n1 - 1, 2):
		if s[a[i]] == s[a[i + 1]]:
			if s[a[i]] == 'A':
				aw += a[i + 1] - a[i] - 1
			else:
				aw -= a[i + 1] - a[i] - 1
	if odd == True:
		if s[a[n1]] == 'A':
			aw += n - a[n1] - 1
		else:
			aw -= n - a[n1] - 1
	if aw > 0:
		print('A')
	else:
		print('B')


import math as ma
import sys
from sys import exit
from decimal import Decimal as dec
from itertools import permutations

def li():
	return list(map(int, input().split()))

def num():
	return map(int, input().split())

def nu():
	return int(input())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = nu()
for it in range(t):
	s = input()
	n = len(s)
	cc = 1
	last = -1
	dir = -1
	ind = -1
	x = [0] * n
	c = 0
	for i in range(n):
		if s[i] == '.':
			continue
		if last == -1:
			if cc % 2 == 1:
				last = s[i]
				dir = 1
				ind = i
			cc += 1
		elif cc % 2 == 0:
			if s[i] == 'A' and last == 'B' or (s[i] == 'B' and last == 'A'):
				c ^= i - ind - 1
				ind = -1
				last = -1
				dir = -1
			else:
				last = s[i]
				dir = -1
				ind = i
			cc += 1
		else:
			last = s[i]
			dir = 1
			ind = i
			cc += 1
	if c == 0:
		last = -1
		ind = -1
		ca = 0
		cb = 0
		cc = 1
		for i in range(n):
			if s[i] == '.':
				continue
			if last == -1:
				if cc % 2 == 1:
					last = s[i]
					ind = i
				cc += 1
			elif cc % 2 == 0:
				if s[i] == 'A' and last == 'A' or (s[i] == 'B' and last == 'B'):
					last = s[i]
					if s[i] == 'A':
						ca += i - ind - 1
					else:
						cb += i - ind - 1
					ind = i
				else:
					last = s[i]
					ind = i
				cc += 1
			else:
				last = s[i]
				ind = i
				cc += 1
		if cc % 2 == 0:
			if last == 'A':
				ca += n - 1 - ind
			else:
				cb += n - 1 - ind
		if cb >= ca:
			print('B')
		else:
			print('A')
	else:
		last = -1
		ind = -1
		ca = 0
		cb = 0
		cc = 1
		for i in range(n):
			if s[i] == '.':
				continue
			if last == -1:
				if cc % 2 == 1:
					last = s[i]
					ind = i
				cc += 1
			elif cc % 2 == 0:
				if s[i] == 'A' and last == 'A' or (s[i] == 'B' and last == 'B'):
					last = s[i]
					if s[i] == 'A':
						ca += i - ind - 1
					else:
						cb += i - ind - 1
					ind = i
				else:
					last = s[i]
					ind = i
				cc += 1
			else:
				last = s[i]
				ind = i
				cc += 1
		if cc % 2 == 0:
			if last == 'A':
				ca += n - 1 - ind
			else:
				cb += n - 1 - ind
		if ca >= cb:
			print('A')
		else:
			print('B')


t = int(input())
for _ in range(t):
	s = input()
	(idx, l, fst, snd, p1, p2, d) = (0, len(s), -1, -1, 0, 0, 0)
	while idx < l:
		while idx < l and s[idx] == '.':
			idx += 1
		if idx < l:
			fst = idx
			idx += 1
		while idx < l and s[idx] == '.':
			idx += 1
		if fst != -1:
			snd = idx
		idx += 1
		if fst != -1 and (snd == l or s[fst] == s[snd]):
			if s[fst] == 'A':
				p1 += snd - fst - 1
			elif s[fst] == 'B':
				p2 += snd - fst - 1
		elif fst != -1:
			d ^= snd - fst - 1
		fst = snd = -1
	if d > 0:
		p1 += 1
	print('B' if p1 <= p2 else 'A')


out = []
tkn = {'.': 0, 'A': 1, 'B': 2}
for ti in range(int(input())):
	board = input().strip()
	state = 0
	moves = [0] * 3
	comp = 0
	zone = 0
	for c in board:
		tc = tkn[c]
		if tc == 0:
			zone += 1
		elif state == tc:
			state = 0
			moves[tc] += zone
		elif state == 0:
			state = tc
			zone = 0
		else:
			state = 0
			comp ^= zone
	if state > 0:
		moves[state] += zone
	if moves[1] > moves[2]:
		out.append('A')
	elif moves[2] > moves[1]:
		out.append('B')
	elif comp > 0:
		out.append('A')
	else:
		out.append('B')
print('\n'.join(out))


for _ in range(int(input())):
	s = input()
	c = 0
	ca = 0
	cb = 0
	ex = 0
	l = None
	k = 0
	for i in range(len(s)):
		if c == 0:
			if s[i] == '.':
				continue
			elif s[i] == 'A':
				l = 'A'
				c = 1
			elif s[i] == 'B':
				l = 'B'
				c = 1
		elif s[i] == '.':
			k += 1
		else:
			c = 0
			if l == 'A' and s[i] == 'A':
				ca += k
			elif l == 'B' and s[i] == 'B':
				cb += k
			else:
				ex = ex ^ k
			k = 0
			l = None
	if l == 'A':
		ca += k
	elif l == 'B':
		cb += k
	if ex:
		ca += 1
	if ca > cb:
		print('A')
	else:
		print('B')