#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
int t;
cin >> t;
while (t--) {
int n;
cin >> n >> s;
int v = 1;
while (v < n) {
if (s[n - 1 - v] == 'A') {
v = 2 * v + 1;
} else {
v = 2 * v;
}
}
cout << 2 * n - v << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJpbmcgczsKCmludCBtYWluKCkKewogICAgaW50IHQ7CiAgICBjaW4gPj4gdDsKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBpbnQgbjsKICAgICAgICBjaW4gPj4gbiA+PiBzOwogICAgICAgIGludCB2ID0gMTsKICAgICAgICB3aGlsZSAodiA8IG4pIHsKICAgICAgICAgICAgaWYgKHNbbiAtIDEgLSB2XSA9PSAnQScpIHsKICAgICAgICAgICAgICAgIHYgPSAyICogdiArIDE7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICB2ID0gMiAqIHY7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dCA8PCAyICogbiAtIHYgPDwgZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9