#P2091. 2024.9.19-MY-第2题-删除字符

2024.9.19-MY-第2题-删除字符

题目内容

小塔拿到了一个长度为nn的字符串ss，但他不喜欢长度大于 11 的回文串。

因此他现在想要任意地删除一些ss中的字母，使得ss不是个长度大于11的回文串，他想知道最少需要删除几个字符，请你帮帮他吧。

输入描述

输入包含若干行。

第一行一个正整数 T(1≤T≤103)T(1 ≤ T ≤ 10^3)，表示测试数据组数。

接下来，对于每组数据。输入包含两行。

第一行一个正整数 n(1≤n≤105)n(1≤n≤10^5)，表示字符串的长度。

第二行一个长度为nn的字符串ss。

(保证所有测试数据的nn的总和不超过 10510^5。)

输出描述

对于每组测试数据，输出一个整数，表示最少的删除次数。

如果是TT 组测试数据的话则需要输出TT 个整数。

样例1

输入

1
4
abba

输出

1

说明

知识点:*****

查看知识点以及同类型题目

Statistics