#P18537. Palworld

Palworld

Palworld

一款名为 Palworld 的新游戏正在风靡全球。游戏目标是构造尽可能长的回文串。这是一款解谜游戏!

游戏开始时,你有一个由 nn 个小写英文字母组成的字符串 SS,以及整数 kk。你必须恰好执行一次以下操作:

  • 选择位置 ii,0≤i≤n0\le i\le n,在 SS 的第 ii 个字符之后插入至多 kk 个字符。i=0i=0 表示在整个 SS 的最前面插入;i=ni=n 表示在最后面插入。

插入的字符形成一个连续块,插入位置只有一个。允许插入零个字符。

游戏分数等于操作后字符串中最长回文子串的长度。请计算可能取得的最高分数。

回文串是正着读、倒着读都相同的字符串。子串通过删除原串前面和/或后面的若干字符得到,允许不删除;必须连续。

输入格式

第一行一个整数 tt,表示测试用例数。每个测试用例占两行:

  • 第一行两个整数 n,kn,k,分别为 SS 的长度和允许插入的最大字符数;
  • 第二行字符串 SS。

限制:

  • 1≤t≤1041\le t\le10^4;
  • 1≤n≤2⋅1051\le n\le2\cdot10^5;
  • 1≤k≤1001\le k\le100;
  • SS 只含 a 到 z;
  • 同一个输入文件中全部测试用例的 nn 之和不超过 2⋅1052\cdot10^5。

输出格式

每个测试用例输出一行,一个整数,表示操作后最长回文子串长度的最大可能值。

原样例

4
1 3
a
4 1
icpc
4 2
icpc
8 4
icecream
4
5
5
11

样例说明

  • 第一例可插入 33 个字符得到 abba,它是长度 44 的回文串。
  • 第二例最优做法是在末尾添加 i,得到长度 55 的回文串 icpci。
  • 第三例即使允许插入 22 个字符,也无法获得更长的回文子串。
  • 第四例的一种最优结果是 imaercecream,其中子串 maercecream 是长度 1111 的回文串。