Chuỗi đặc biệt của FullHouse Dev

Bối cảnh

FullHouse Dev đang nghiên cứu về một loại chuỗi đặc biệt. Bạn được giao nhiệm vụ giúp FullHouse Dev xử lý các chuỗi này.

Yêu cầu

Bạn được cho một chuỗi S có độ dài N. Nhiệm vụ của bạn là xóa một dãy con có độ dài tối đa từ chuỗi, sao cho sau khi nối các phần còn lại của chuỗi, nó trở thành một palindrome có độ dài lớn hơn 1.

Nếu điều này có thể thực hiện được, hãy in ra độ dài tối đa của dãy con có thể xóa. Ngược lại, hãy in ra -1.

Input

• Dòng đầu tiên chứa một số nguyên T - số lượng bộ test.
• Mỗi bộ test gồm 2 dòng:
  • Dòng đầu tiên chứa một số nguyên N - độ dài của chuỗi S.
  • Dòng thứ hai chứa chuỗi S, bao gồm các chữ cái tiếng Anh viết thường.

Output

• Với mỗi bộ test, nếu có thể xóa một dãy con theo điều kiện đã cho, in ra một số nguyên duy nhất biểu thị độ dài tối đa của dãy con có thể xóa. Ngược lại, in ra -1.

Ràng buộc

• 1 ≤ T ≤ 2500
• 3 ≤ N ≤ 100
• S chỉ bao gồm các chữ cái tiếng Anh viết thường.

Ví dụ 1

Input

3
6
babkhj
3
abc
4
qtoo

Output

4
-1
2

Giải thích ví dụ

• Test 1: Có thể xóa dãy con "akhj" để được palindrome "bb". Đây là dãy con dài nhất có thể xóa, có độ dài 4.
• Test 2: Không thể xóa bất kỳ dãy con nào để tạo thành palindrome có độ dài lớn hơn 1.
• Test 3: Có thể xóa dãy con "qt" để được palindrome "oo". Đây là dãy con duy nhất có thể xóa, có độ dài 2.

Thông tin học tập

• Buổi: B20
• Concepts: std::string, getline, index, find, substr, basic transformations
• Giới hạn kiến thức: B01-B20
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 10