CF1791C.Prepend and Append
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Timur initially had a binary string † s (possibly of length 0 ). He performed the following operation several (possibly zero) times:
- Add 0 to one end of the string and 1 to the other end of the string. For example, starting from the string 1011 , you can obtain either 010111 or 110110 .
You are given Timur's final string. What is the length of the shortest possible string he could have started with? † A binary string is a string (possibly the empty string) whose characters are either 0 or 1 .
输入格式
The first line of the input contains an integer t ( 1≤t≤100 ) — the number of testcases.
The first line of each test case contains an integer n ( 1≤n≤2000 ) — the length of Timur's final string.
The second line of each test case contains a string s of length n consisting of characters 0 or 1 , denoting the final string.
输出格式
For each test case, output a single nonnegative integer — the shortest possible length of Timur's original string. Note that Timur's original string could have been empty, in which case you should output 0 .
输入输出样例
输入#1
9 3 100 4 0111 5 10101 6 101010 7 1010110 1 1 2 10 2 11 10 1011011010
输出#1
1 2 5 0 3 1 0 2 4
说明/提示
In the first test case, the shortest possible string Timur started with is 0 , and he performed the following operation: 0→100 .
In the second test case, the shortest possible string Timur started with is 11 , and he performed the following operation: 11→0111 .
In the third test case, the shortest possible string Timur started with is 10101 , and he didn't perform any operations.
In the fourth test case, the shortest possible string Timur started with is the empty string (which we denote by ε ), and he performed the following operations: ε→10→0101→101010 .
In the fifth test case, the shortest possible string Timur started with is 101 , and he performed the following operations: 101→01011→1010110 .