Ненеспадаючі масиви#12882

Ненеспадаючі масиви

1 second
256 megabytes
Medium

Масив b_1, b_2, \ldots, b_m називається неспадаючим, якщо b_1 \le b_2 \ldots \le b_m. Інакше масив називається ненеспадаючим.

Вам дано ненеспадаючий масив a_1, a_2, \ldots, a_n. Ви хочете розбити його на максимальну кількість послідовних підмасивів, кожен з яких є ненеспадаючим. На яку максимальну кількість підмасивів ви можете розбити ?

Input

Перший рядок містить єдине ціле число (1 \le t \le 10^4)  — кількість наборів вхідних даних. Далі слідує опис наборів вхідних даних.

Перший рядок кожного набору вхідних даних містить одне ціле число (2 \le n \le 2\cdot 10^5)  — довжину масиву.

Другий рядок кожного набору вхідних даних містить цілих чисел a_1, a_2, \ldots, a_n (0 \le a_i \le 10^6).

Гарантується, що масив є ненеспадаючим.

Гарантується, що сума по всім наборам вхідних даних не перевищує 2\cdot 10^5.

Output

Для кожного набору вхідних даних виведіть єдине ціле число  — максимальну можливу кількість ненеспадаючих підмасивів, на яку можна розбити .

Examples

Example 1

Loading
Loading

Note

В першому наборі вхідних даних, можна розбити масив на три підмасиви [1, 0], [1, 0], [1, 0].

В другому наборі вхідних даних, не можна розбити масив на більше ніж один ненеспадаючий підмасив.

В третьому наборі вхідних даних, можна розбити масив на три підмасиви [100, 10], [1, 100, 10, 1, 100], [10, 1].