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(al..r)}\right)), where (al..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).