B'This is the easy version of this problem. The difference between easy and hard versions is only the constraints on a_i and on n . You can make hacks only if both versions of the problem are solved. Burenka is the crown princess of Buryatia, and soon she will become the n -th queen of the country. There is an ancient tradition in Buryatia -- before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the n -th ruler, the inhabitants of the country give them an array of a of exactly n numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times: Help Burenka calculate how much time she will need. The first line contains a single integer t ( 1 <= t <= 500 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer n ( 1 <= n <= 5000 ) -- the size of the array. The second line of each test case contains n integers a_1, a_2, ldots, a_n ( 0 <= a_i <= 5000 ) -- elements of the array. It is guaranteed that the sum of n in all tests does not exceed 5000 . For each test case, output a single number -- the minimum time that Burenka will need. In the first test case, Burenka can choose segment l = 1 , r = 4 , and x=5 . so it will fill the array with zeros in 2 seconds. In the second test case, Burenka first selects segment l = 1 , r = 2 , and x = 1 , after which a = [0, 2, 2] , and then the segment l = 2 , r = 3 , and x=2 , which fills the array with zeros. In total, Burenka will spend 2 seconds. '...