CF1582E Pchelyonok and Segments

Pchelyonok decided to give Mila a gift. Pchelenok has already bought an array $ a $ of length $ n $ , but gifting an array is too common. Instead of that, he decided to gift Mila the segments of that array! Pchelyonok wants his gift to be beautiful, so he decided to choose $ k $ non-overlapping segments of the array $ [l_1,r_1] $ , $ [l_2,r_2] $ , $ \ldots $ $ [l_k,r_k] $ such that: - the length of the first segment $ [l_1,r_1] $ is $ k $ , the length of the second segment $ [l_2,r_2] $ is $ k-1 $ , $ \ldots $ , the length of the $ k $ -th segment $ [l_k,r_k] $ is $ 1 $ - for each $ i

The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The next $ 2 \cdot t $ lines contain the descriptions of test cases. The description of each test case consists of two lines. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

For each test case, print the maximum possible value of $ k $ .