F. Make a Palindrometime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou 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$$$.InputThe 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$$$.OutputFor each test case, print a single integer — the sum of the values of the function $$$f$$$ for all subarrays of the array $$$a$$$.ExampleInput432 1 341 1 1 154 2 3 1 541 2 1 2Output3
0
14
5