11240 - Antimonotonicity

給定一個稱為Fred的數列，共有 n 項，且每一項的數值分別介於 1~n 之間，任一對相鄰的項其值必不相同，本題要求從Fred數列中找出稱為Mary的最長子序列滿足下列性質：

Mary[0] > Mary[1] < Mary[2] > Mary[3] < ...

Input

輸入資料的第一列有一個整數T表示測試資料的組數，T最大為50，接著有T組測試資料。每組測試資料一列，該列的第一個整數 n 表示Fred數列的項數，接下來有 n 個整數依序為數列的每一項，n 最大為30000，項與項之間以一個空白字元隔開，且每組資料的前後不會有多餘的空白字元。

Output

請對每組測試資料輸出最長子序列Mary共有幾項。

Sample Input

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

Sample Output

1
2
5
3

---

原文出處