#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    if (n % 2 == 1) {
      cout << "NO" << '\n';
      continue;
    }
    cout << "YES" << '\n';
    for (int i = 0; i < n / 2; ++i)
      for (int j = 0; j < 2; ++j)
        cout << "AB"[i & 1];
    cout << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    vector<int> b({a[n - 1]});
    for (int i = n - 2; i >= 0; --i) {
      if (a[i] > b.back()) {
        b.push_back(a[i] % 10);
        b.push_back(a[i] / 10);
      } else {
        b.push_back(a[i]);
      }
    }
    cout << (is_sorted(b.rbegin(), b.rend()) ? "YES" : "NO") << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<char> ok1(n / 2), ok2(n / 2);
    for (int i = 0; i < 2; ++i) {
      string s;
      cin >> s;
      for (int j = 0; j < n; ++j) if ((i + j) & 1) {
        ok1[(i + j) / 2] |= (s[j] == '>');
        ok2[(j - i + 1) / 2] |= (s[j] == '>');
      }
    }
    bool ans = true;
    for (int i = 0; i < n / 2; ++i) ans &= ok1[i] && ok2[i];
    cout << (ans ? "YES" : "NO") << '\n';
  }
}

for _ in range(int(input())):
    s = input()
    n = len(s)
    ans = 0
    for d in range(1, n // 2 + 1):
        cnt = 0
        for i in range(n - d):
            cnt += s[i] == s[i + d] or s[i] == '?' or s[i + d] == '?'
            if i - d >= 0:
                cnt -= s[i - d] == s[i] or s[i - d] == '?' or s[i] == '?'
            if i - d >= -1 and cnt == d:
                ans = 2 * d
    print(ans)

#include<bits/stdc++.h>
 
using namespace std;
 
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n), c(n);
    for(int i = 0; i < n; i++)
    {
        a[i] = i + 1;
        c[i] = i / k + 1;
    }
    int q = *max_element(c.begin(), c.end());
    for(int i = 1; i <= q; i++)
    {
        int l = find(c.begin(), c.end(), i) - c.begin();
        int r = c.rend() - find(c.rbegin(), c.rend(), i);
        int m = (l + r) / 2;
        reverse(a.begin() + l, a.begin() + m);
        reverse(a.begin() + m, a.begin() + r);
    }
    for(int i = 0; i < n; i++)
        cout << a[i] << " \n"[i == n - 1];
    cout << q << "\n";
    for(int i = 0; i < n; i++)
        cout << c[i] << " \n"[i == n - 1];
}
 
int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

#include <bits/stdc++.h>
 
using namespace std;

const int MOD = 998244353;

int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  return x;
}

int mul(int x, int y) {
  return x * 1LL * y % MOD;
}

int binpow(int x, int y) {
  int z = 1;
  while (y) {
    if (y & 1) z = mul(z, x);
    x = mul(x, x);
    y >>= 1;
  }
  return z;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n), b(n);
  for (auto& x : a) cin >> x;
  for (auto& x : b) cin >> x;
  vector<int> suma(n + 1), sumb(n + 1);
  for (int i = 0; i < n; ++i) {
    suma[i + 1] = suma[i] + a[i];
    sumb[i + 1] = sumb[i] + b[i];
  }
  int m = sumb[n];
  vector<int> f(m + 1), invf(m + 1);
  f[0] = 1;
  for (int i = 1; i <= m; ++i) f[i] = mul(f[i - 1], i);
  invf[m] = binpow(f[m], MOD - 2);
  for (int i = m; i > 0; --i) invf[i - 1] = mul(invf[i], i);
  vector<int> sumc(m + 2);
  for (int i = 0; i <= m; ++i)
    sumc[i + 1] = add(sumc[i], mul(f[m], mul(invf[i], invf[m - i])));
  int pw2 = binpow(binpow(2, MOD - 2), m);
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l;
    int k = 2 * (suma[r] - suma[l]) - suma[n];
    int cur = sumb[r] - sumb[l];
    int mx = max(0, min(k + cur, m + 1));
    int cnt = sumc[mx];
    cout << mul(cnt, pw2) << ' ';
  }
}

#include<bits/stdc++.h>

using namespace std;

int n, c;
int g[21][21];

const int INF = int(1e9);

int primMST(int vertex_cover_mask)
{
    vector<int> d(n, INF);
    vector<bool> used(n, false);
    d[0] = 0;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int idx = -1;
        for(int j = 0; j < n; j++)
        {
            if(!used[j] && d[j] < INF && (idx == -1 || d[j] < d[idx]))
                idx = j;
        }
        if(idx == -1) return INF;
        used[idx] = true;
        ans += d[idx];
        for(int k = 0; k < n; k++)
        {
            if(used[k]) 
                continue;
            if((vertex_cover_mask & (1 << idx)) == 0 && (vertex_cover_mask & (1 << k)) == 0)
                continue;
            d[k] = min(d[k], g[idx][k]);
        }
    }
    return ans;
}

int main()
{
    cin >> n >> c;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> g[i][j];
            if(g[i][j] == 0) g[i][j] = INF;
        }
    }
    int ans = INF;
    for(int mask = 0; mask < (1 << n); mask++)
    {
        int cur = primMST(mask);
        if(cur != INF) ans = min(ans, cur + c * __builtin_popcount(mask));
    }
    cout << ans << endl;
}