Given a string S of size N, made up of only 3 characters a, b, c . Find the number of subsequences of String S of length 3 which are palindrome. A palindrome is a string that reads the same backward as forward.
Given T test case,
Each test case consists of 2 lines
Line 1 contains a number N denoting the size of the string
Line 2 contains the String S
Print a single integer for each test case which is the number of subsequences of string S of length 3 which are palindrome.
In first test case
String S = abbca , palindromic subsequences are [ { 0,1,4 } , {0,2,4} , {0,3,4} ] , so answer = 3
Note:- here 0,1,2,3,4 are indexes of characters taken in the subsequence
In second test case
String S = abcabc, palindromic subsequences are [ {0,1,3} , {0,2,3} , {1,2,4} , {1,3,4} , {2,3,5} , {2,4,5} ] , so answer = 6