#include <iostream>
 
using namespace std;
 
int main()
{
	int t, n, *li, x, p = 0, k = 0;
	char *tab;
 
	cin >> t;
 
	for (int i = 0; i < t; i++)
	{
		cin >> n;
 
		tab = new char[n - 1];
		li = new int[n - 1];
 
		getchar();
 
		for (int j = 0; j < n - 1; j++)
		{
			tab[j] = getchar();
			li[j] = j + 1;
		}
		li[n - 1] = n;
 
		x = n;
 
		while (x != 1)
		{
 
			for (int a = 0; a < x; a += 2)
			{
				if (tab[k] == 'A')
				{
					li[p] = li[a];
				}
				else
				{
					li[p] = li[a + 1];
				}
				k++;
				p++;
			}
			x /= 2;
			p = 0;
 
		}
 
		cout << li[0] << endl;
		k = 0;
		delete[] tab;
		delete[] li;
	}
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkKewoJaW50IHQsIG4sICpsaSwgeCwgcCA9IDAsIGsgPSAwOwoJY2hhciAqdGFiOwoKCWNpbiA+PiB0OwoKCWZvciAoaW50IGkgPSAwOyBpIDwgdDsgaSsrKQoJewoJCWNpbiA+PiBuOwoKCQl0YWIgPSBuZXcgY2hhcltuIC0gMV07CgkJbGkgPSBuZXcgaW50W24gLSAxXTsKCgkJZ2V0Y2hhcigpOwoKCQlmb3IgKGludCBqID0gMDsgaiA8IG4gLSAxOyBqKyspCgkJewoJCQl0YWJbal0gPSBnZXRjaGFyKCk7CgkJCWxpW2pdID0gaiArIDE7CgkJfQoJCWxpW24gLSAxXSA9IG47CgoJCXggPSBuOwoKCQl3aGlsZSAoeCAhPSAxKQoJCXsKCgkJCWZvciAoaW50IGEgPSAwOyBhIDwgeDsgYSArPSAyKQoJCQl7CgkJCQlpZiAodGFiW2tdID09ICdBJykKCQkJCXsKCQkJCQlsaVtwXSA9IGxpW2FdOwoJCQkJfQoJCQkJZWxzZQoJCQkJewoJCQkJCWxpW3BdID0gbGlbYSArIDFdOwoJCQkJfQoJCQkJaysrOwoJCQkJcCsrOwoJCQl9CgkJCXggLz0gMjsKCQkJcCA9IDA7CgoJCX0KCgkJY291dCA8PCBsaVswXSA8PCBlbmRsOwoJCWsgPSAwOwoJCWRlbGV0ZVtdIHRhYjsKCQlkZWxldGVbXSBsaTsKCX0KCglyZXR1cm4gMDsKfQ==

Mwo4CkFCQUFBQkIKMTYKQUJBQUFBQkJBQUFCQUJCCjMyCkFCQUFCQkJBQUFCQUJBQkJBQkFBQUFBQUFBQUFCQUE=

3
8
ABAAABB
16
ABAAAABBAAABABB
32
ABAABBBAAABABABBABAAAAAAAAAABAA