q = int(input())
 
for _ in range(q):
    n, k = map(int, input().split())
    s = input()
    if s == s[::-1] or k == 0:
        print(1)
    else:
        print(2)

def main():
    n, x, y = map(int, input().split())
    a = list(map(int, input().split()))
    if (sum(a) + x + y) % 2 == 0:
        print('Alice')
    else:
        print('Bob')
 
 
for _ in range(int(input())):
    main()

def solve():
    n, k = map(int, input().split())
    if k == 1:
        print("YES")
        for i in range(1, n + 1):
            print(i)
        return
 
    if n % 2 == 1:
        print("NO")
        return
 
    print("YES")
    for i in range(1, n + 1):
        print(*[i for i in range(i, n * k + 1, n)])
 
 
for _ in range(int(input())):
    solve()

#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
 
using namespace std;
 
 
int get(const vector <int>& x) {
    cout << "? " << x[0] + 1 << " " << x[1] + 1 << " " << x[2] + 1 << endl;
    int ans;
    cin >> ans;
    return ans;
}
 
 
signed main() {
    ios_base::sync_with_stdio();
    cin.tie(nullptr);
 
    int n;
    cin >> n;
 
    pair <int, int> possible = {0, 1};
    for (int i = 2; i < n - 1; i += 2) {
        vector <pair <int, int>> ch(4);
        vector <int> now = {possible.first, possible.second, i, i + 1};
        for (int j = 0; j < 4; j++) {
            vector <int> x = now;
            x.erase(x.begin() + j);
            ch[j] = {get(x), now[j]};
        }
        sort(all(ch));
        possible = {ch[0].second, ch[1].second};
    }
    if (n % 2 == 1) {
        int other = 0;
        while (possible.first == other || possible.second == other) {
            other++;
        }
        vector <pair <int, int>> ch(4);
        vector <int> now = {possible.first, possible.second, n - 1, other};
        for (int j = 0; j < 4; j++) {
            vector <int> x = now;
            x.erase(x.begin() + j);
            ch[j] = {get(x), now[j]};
        }
        sort(all(ch));
        possible = {ch[0].second, ch[1].second};
    }
    cout << "! " << possible.first + 1 << " " << possible.second + 1 << endl;
    return 0;
}

#include <bits/stdc++.h>
 
#define len(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define endl "\n"
 
using namespace std;
 
const int N = 4e5 + 100, H = 2e5 + 50;
vector <pair <int, int>> g[N];
string ans[N];
int pos[N];
 
 
void dfs(int v) {
    if (pos[v] == 0) {
        ans[v] = string(len(g[v]), 'L');
    }
 
    while (pos[v] < len(g[v])) {
        auto [i, ind] = g[v][pos[v]];
        if (i == -1) {
            pos[v]++;
            continue;
        }
        g[i][ind].first = -1, g[v][pos[v]].first = -1;
        if (v < H) {
            ans[v][pos[v]] = 'R';
        }
        pos[v]++;
        dfs(i);
    }
}
 
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int m;
    cin >> m;
    map <int, int> ind, cnt;
    int fre_ind = 0;
 
    vector <vector <int>> nums(m);
    for (int i = 0; i < m; i++) {
        int n;
        cin >> n;
        for (int _ = 0; _ < n; _++) {
            int x;
            cin >> x;
            if (!ind.count(x)) {
                ind[x] = fre_ind++;
            }
            x = ind[x];
            cnt[x]++;
            nums[i].push_back(x);
            g[i].emplace_back(x + H, len(g[x + H]));
            g[x + H].emplace_back(i, len(g[i]) - 1);
        }
    }
 
    for (auto [num, cn] : cnt) {
        if (cn % 2 == 1) {
            cout << "NO" << endl;
            return 0;
        }
    }
 
    for (int i = 0; i < N; i++) {
        dfs(i);
    }
 
    cout << "YES" << endl;
    for (int i = 0; i < m; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
#define endl "\n"
#define int long long
 
using namespace std;
 
const int N = 3e5 + 100;
int MOD;
int fib[N];
 
vector <int> unfib;
int notzero = 0;
 
void upd(int ind, int delta) {
  notzero -= (unfib[ind] != 0);
  unfib[ind] += delta;
  if (unfib[ind] >= MOD) {
    unfib[ind] -= MOD;
  };
  notzero += (unfib[ind] != 0);
}
 
 
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
 
  int n, q;
  cin >> n >> q >> MOD;
 
  fib[0] = fib[1] = 1;
  for (int i = 2; i < N; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  }
 
  vector <int> delta(n);
  for (int& i : delta) {
    cin >> i;
  }
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    delta[i] = (delta[i] - x + MOD) % MOD;
  }
 
  unfib.resize(n);
  unfib[0] = delta[0];
  if (len(unfib) >= 2) {
    unfib[1] = (delta[1] - delta[0] + MOD) % MOD;
  }
  for (int i = 2; i < n; i++) {
    unfib[i] = ((long long) delta[i] - delta[i - 1] - delta[i - 2] + MOD * 2) % MOD;
  }
  for (int i = 0; i < n; i++) {
    notzero += (unfib[i] != 0);
  }
 
  while (q--) {
    char c;
    int l, r;
    cin >> c >> l >> r;
    if (c == 'A') {
      upd(l - 1, 1);
      if (r != n) {
        upd(r, MOD - fib[r - l + 1]);
      }
      if (r < n - 1) {
        upd(r + 1, MOD - fib[r - l]);
      }
    } else {
      upd(l - 1, MOD - 1);
      if (r != n) {
        upd(r, fib[r - l + 1]);
      }
      if (r < n - 1) {
        upd(r + 1, fib[r - l]);
      }
    }
    if (!notzero) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }
  return 0;
}