Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

EP-Palindromes

By Hasinur_ · Limits 2s, 512 MB

You will be given an array of integers AA. You have to count the number of subarrays\textbf{subarrays} (a non-empty sequence of consecutive elements of an array) of AA that are EP-Palindrome.

Definition of EP-Palindrome

An array VV is EP-Palindrome if Vmod2=0|V|\mod 2 = 0 and rearranging the elements in VV can form a palindrome. Here, V|V| denotes the number of elements in VV, also known as the length of VV. For example, let V=[1,2,1,2]V=[1,2,1,2] where Vmod2=0|V|\mod 2 = 0. We can get V=[1,2,2,1]V= [1,2,2,1] or V=[2,1,1,2]V= [2,1,1,2] by rearranging the elements of VV. So, V=[1,2,1,2]V=[1,2,1,2] is an EPPalindromeEP-Palindrome.

Input

The first line of the input file will contain an integer T(1T30)T (1\leq T\leq 30) which denotes the number of test cases.
Then there will be TT test cases.

The first line of each test case will contain a single integer N(1N105)N (1\leq N\leq10^{5}), denoting the size of the array AA.

The second line of each test case will contain NN integers A[1],A[2],,A[N]A[1], A[2], \dots, A[N] which are the elements of the array. Here, the ithi^{th} integer denotes the element A[i](1A[i]2×106)A[i] (1\leq A[i]\leq 2\times10^{6}).

Output

For each test case, print "Case X: Y\textbf{Case X: Y}" without the quotation symbol, where XX is the case number and YY is the number of EPPalindromicEP-Palindromic subarrays of AA.

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]A[ ]=[1,1,1].
Subarrays of AA are [1],[1],[1],[1,1],[1,1],[1,1,1][1],[1],[1],[1,1],[1,1],[1,1,1]

Now,

  • [1][1] has length =1= 1, 1mod201 \mod 2 \neq 0. So, it's not EP-Palindrome.
  • [1][1] has length =1= 1, 1mod201 \mod 2 \neq 0. So, it's not EP-Palindrome.
  • [1][1] has length =1= 1, 1mod201 \mod 2 \neq 0. So, it's not EP-Palindrome.
  • [1,1][1,1] has length =2= 2, 2mod2=02 \mod 2 = 0. The subarray is a palindrome already. So, it’s EP-Palindrome\textbf{it's EP-Palindrome}.
  • [1,1][1,1] has length =2= 2, 2mod2=02 \mod 2 = 0. The subarray is a palindrome already. So, it’s EP-Palindrome\textbf{it's EP-Palindrome}.
  • [1,1,1][1,1,1] has length =3= 3, 3mod203 \mod 2 \neq 0. So, it's not EP-Palindrome.

The array AA has 22 subarrays in total which are EP-Palindromes\textbf{EP-Palindromes}

Discussion

Statistics


62% Solution Ratio

aniks2645Earliest, Sep '20

pathanFastest, 0.7s

Test2311Lightest, 7.3 MB

RUHRUHShortest, 531B

Submit

Login to submit

Editorial

Let's first solve the problem considering the array as a string with lowercase latin letters. Then t...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.