B'Milena has received an array of integers a_1, a_2, ldots, a_n of length n from a secret admirer. She thinks that making it non-decreasing should help her identify the secret admirer. She can use the following operation to make this array non-decreasing: More formally, let a_1, a_2, ldots, a_i, ldots, a_k be an array a before the operation. After the operation, it becomes equal to a_1, a_2, ldots, a_{i-1}, x, a_i - x, a_{i+1}, ldots, a_k . Note that the length of a increases by 1 on each operation. Milena can perform this operation multiple times (possibly zero). She wants you to determine the minimum number of times she should perform this operation to make array a non-decreasing. An array x_1, x_2, ldots, x_k of length k is called non-decreasing if x_i <= x_{i+1} for all 1 <= i < k . Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= q t <= q 10 ,000 ). The description of test cases follows. The first line of each test case contains a single integer n ( 1 <= q n <= q 2 cdot 10^5 ) -- the length of the array a . The second line of each test case contains n integers a_1, a_2, ldots, a_n ( 1 <= q a_i <= q 10^9 ) xe2 x80 x93 the array a . It is guaranteed that the sum of n over all test cases does not exceed 2 cdot 10^5 . For each test case, output one integer -- the minimum number of operations required to make the array non-decreasing. It can be shown that it is always possible to make the array a non-decreasing in the finite number of operations. In the first test case, Milena can replace the second element of array a by integers 1 and 2 , so the array would become [ , 1, , underline{1}, , underline{2}, , 2 ,] . Only 1 operation is required. In the second test case, the array a is already non-decreasing, so the answer is 0 . In the '...