Counting Palindromic Subarrays

You are given an array of integers. Your task is to count the number of contiguous subarrays (subsegments) that are palindromic. A subarray is palindromic if it reads the same forward and backward. Note that each single element is considered a palindrome.

Definition:

• A subarray of an array A is defined by a pair of indices (i, j) with 0 ≤ i ≤ j < N, and consists of the sequence A[i], A[i+1], …, A[j].
• A subarray is palindromic if it is equal to its reverse. In other words, A[i..j] is a palindrome if:

$$A[i] = A[j], \; A[i+1] = A[j-1], \; \ldots$$

Input/Output Requirements:

The solution should read from stdin and write to stdout.

inputFormat

The first line of input contains an integer T, representing the number of test cases. For each test case, the first line contains an integer N, the number of elements in the array. The second line contains N space-separated integers.

outputFormat

For each test case, print a single integer on a new line — the total number of palindromic subarrays in the given array.## sample

1
1
42

1