EP-Palindromes

Hasinur_ Criterion 2020 Round 7
Limits 2s, 512 MB

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

InputOutput
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}$

Submit

Login to submit.

Statistics

63% Solution Ratio
aniks2645Earliest, Sep '20
samiulsamiFastest, 0.6s
Test2311Lightest, 7.3 MB
RUHRUHShortest, 531B
Toph uses cookies. By continuing you agree to our Cookie Policy.