You are given an array $a$ consisting of $n$ integers.

Let the function $f(b)$ return the minimum number of operations needed to make an array $b$ a palindrome. The operations you can make are:

• choose two adjacent elements $b_i$ and $b_{i+1}$, remove them, and replace them with a single element equal to $(b_i + b_{i + 1})$;
• or choose an element $b_i > 1$, remove it, and replace it with two positive integers $x$ and $y$ ($x > 0$ and $y > 0$) such that $x + y = b_i$.

For example, from an array $b=[2, 1, 3]$, you can obtain the following arrays in one operation: $[1, 1, 1, 3]$, $[2, 1, 1, 2]$, $[3, 3]$, $[2, 4]$, or $[2, 1, 2, 1]$.

Calculate $\displaystyle \left(\sum_{1 \le l \le r \le n}{f(a[l..r])}\right)$, where $a[l..r]$ is the subarray of $a$ from index $l$ to index $r$, inclusive. In other words, find the sum of the values of the function $f$ for all subarrays of the array $a$.

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$).

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2000$.

For each test case, print a single integer — the sum of the values of the function $f$ for all subarrays of the array $a$.