You will be given an array of integers $A$. You have to count the number of $\textbf{subarrays}$ (a non-empty sequence of consecutive elements of an array) of $A$ that are EP-Palindrome.
Definition of EP-Palindrome
An array
$V$is EP-Palindrome if$|V|\mod 2 = 0$and rearranging the elements in$V$can form a palindrome. Here,$|V|$denotes the number of elements in$V$, also known as the length of$V$. For example, let$V=[1,2,1,2] $where$|V|\mod 2 = 0$. We can get$V= [1,2,2,1]$or$V= [2,1,1,2] $by rearranging the elements of$V$. So,$V=[1,2,1,2] $is an$EP-Palindrome$.
Input
The first line of the input file will contain an integer $T (1\leq T\leq 30)$ which denotes the number of test cases.
Then there will be $T$ test cases.
The first line of each test case will contain a single integer $N (1\leq N\leq10^{5})$, denoting the size of the array $A$.
The second line of each test case will contain $N$ integers $A[1], A[2], \dots, A[N]$ which are the elements of the array. Here, the $i^{th}$ integer denotes the element $A[i] (1\leq A[i]\leq 2\times10^{6})$.
Output
For each test case, print "$\textbf{Case X: Y}$" without the quotation symbol, where $X$ is the case number and $Y$ is the number of $EP-Palindromic$ subarrays of $A$.
Sample
| Input | Output |
|---|---|
2 3 1 1 1 4 1 2 1 2 | Case 1: 2 Case 2: 1 |
In the sample input, the first test case contains an array $A[ ]=[1,1,1]$.
Subarrays of $A$ are $[1],[1],[1],[1,1],[1,1],[1,1,1]$
Now,
$[1]$has length$= 1$,$1 \mod 2 \neq 0$. So, it's not EP-Palindrome.$[1]$has length$= 1$,$1 \mod 2 \neq 0$. So, it's not EP-Palindrome.$[1]$has length$= 1$,$1 \mod 2 \neq 0$. So, it's not EP-Palindrome.$[1,1]$has length$= 2$,$2 \mod 2 = 0$. The subarray is a palindrome already. So,$\textbf{it's EP-Palindrome}$.$[1,1]$has length$= 2$,$2 \mod 2 = 0$. The subarray is a palindrome already. So,$\textbf{it's EP-Palindrome}$.$[1,1,1]$has length$= 3$,$3 \mod 2 \neq 0$. So, it's not EP-Palindrome.
The array $A$ has $2$ subarrays in total which are $\textbf{EP-Palindromes}$
