1-3 Palindrome

You are given a string 'S'. You perform the following operations:

1. Split 'S' into three non-empty substrings such that each character of 'S' should present in exactly one substring.
2. Create a new string by concatenating 1st and 3rd parts.

Return 1 if you can make this new string a palindrome otherwise return 0.

For Example:-

Let 'N' = 6, 'S' = "abccba".
Three substrings are "ab", "cc", and "ba" and by concatenating 1st and 3rd parts we get "abba" which is a palindrome.
So our answer is 1.

Input Format:-

First-line contains an integer 'T', which denotes the number of test cases.
For every test case:-
First-line contains an integer 'N', denoting the length of the string 'S'.
Second-line contains a String 'S', which consists of 'N' lowercase English letters.

Output Format:-

For each test case, Return 1 if you can make this new string a palindrome otherwise return 0.

Note:-

You don’t need to print anything. Just implement the given function.

Constraints:-

1 <= 'T' <= 10
3 <= 'N' <= 10^5
'S' consists of 'N' lowercase English letters.

The Sum of 'N' overall test cases does not exceed 10^5.
Time Limit: 1 sec