#include <algorithm> #include <cstdio> #include <iostream> #include <string> #include <utility> #include <vector> using namespace std; using i64 = long long; using u64 = unsigned long long; constexpr int N = 5e6, B = 2333; int type; u64 base[N + 1]; void prepare() { base[0] = 1; for (int i = 1; i <= N; ++i) base[i] = base[i - 1] * B; } struct Solution { int n; string s; vector<u64> hsh; u64 get_hash(int l, int r) { return hsh[r] - (l > 0 ? hsh[l - 1] : 0); } bool is_equal(int l1, int r1, int l2, int r2) { if (l1 > l2) { swap(l1, l2); swap(r1, r2); } return get_hash(l1, r1) * base[l2 - l1] == get_hash(l2, r2); } int get_lcp(int l1, int r1, int l2, int r2) { int l = 1, r = min(r1 - l1, r2 - l2) + 1; while (l < r) { int mid = (l + r + 1) >> 1; if (is_equal(l1, l1 + mid - 1, l2, l2 + mid - 1)) l = mid; else r = mid - 1; } return is_equal(l1, l1 + l - 1, l2, l2 + l - 1) ? l : 0; } int solve_max() { int ans = 0, i = 0; if (n <= 5000) { for (; i < n; ++i) { for (int j = i + 1; j < n && (n << 1) - i - j >= ans; ++j) ans = max(ans, (n << 1) - i - j - (get_lcp(i, n - 1, j, n - 1) << 1)); } } else { for (int j = 1; j < n; ++j) ans = max(ans, (n << 1) - i - j - (get_lcp(i, n - 1, j, n - 1) << 1)); } return ans; } int solve_min() { int ans = 1 + ((s[n - 1] != s[n - 2]) << 1); if (n > 2 && s[n - 1] == s[n - 3]) ans = min(ans, 2); return ans; } void main() { cin >> s; n = s.size(); hsh.resize(n); for (int i = 0; i < n; ++i) hsh[i] = (i > 0 ? hsh[i - 1] : 0) + s[i] * base[i]; if (type == 0) cout << solve_max() << '\n'; else if (type == 1) cout << solve_min() << '\n'; else cout << solve_max() << ' ' << solve_min() << '\n'; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; cin >> T >> type; prepare(); while (T-- > 0) Solution().main(); cout << flush; return 0; }