Minimum Increasing Subsequence Partitioning

Emma is given a sequence of n positive integers \(a_1, a_2, \ldots, a_n\). She wants to partition this sequence into the minimum number of contiguous segments such that each segment is strictly increasing. In other words, she seeks the smallest integer \(k\) for which the sequence can be divided into \(k\) segments \([l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]\) where for every segment and for all valid indices \(i\), the condition \(a_i < a_{i+1}\) holds. Your task is to determine this minimum \(k\) for each test case.

inputFormat

The first line of input contains an integer t representing the number of test cases. For each test case, the first line contains an integer n denoting the number of elements in the sequence, and the second line contains n space-separated positive integers.

outputFormat

For each test case, output a single line with one integer: the minimum number of strictly increasing contiguous segments into which the sequence can be partitioned.

3
5
1 2 3 4 5
4
4 3 2 1
6
1 3 2 4 5 6

1
4
2