S2C

Fie un șir format din $N$ numere naturale nenule: $a_1, a_2, \dots, a_N$. Se numește subșir 2-crescător de lungime $k$ al șirului dat orice subșir $a_{x_1}, a_{x_2}, \dots, a_{x_k}$, unde $1 \le x_1 \lt x_2 \lt \dots \lt x_k \le N$, în care este îndeplinită următoarea proprietate:

• $a_{x_i} \lt a_{x_{i+2}}$, pentru orice $i$, $1 \le i \le k - 2$, adică $a_{x_1} \lt a_{x_3} \lt a_{x_5} \lt \dots$ și $a_{x_2} \lt a_{x_4} \lt a_{x_6} \lt \dots$.

Cerință

Date fiind $T$ șiruri conform enunțului, se cere să se determine lungimea maximă a câte unui subșir 2-crescător pentru fiecare dintre cele $T$ șiruri date.

Date de intrare

În fișierul de intrare s2c.in se află pe prima linie numărul $T$, reprezentând numărul de șiruri, iar pe fiecare dintre următoarele $2 \cdot T$ linii se află descrierile șirurilor. Pe linia $2 \cdot i$, se va afla un singur număr natural reprezentând numărul de elemente $N_i$ al celui de-al $i$-lea șir de numere dat. Pe linia $2 \cdot i + 1$ se vor afla $N_i$ numere naturale, reprezentând numerele din șir, separate prin câte un spațiu.

Date de ieșire

În fișierul de ieșire s2c.out se va scrie pe fiecare dintre $T$ linii, fiecare conținând un singur număr natural. Pe linia $i$ se va scrie un număr natural reprezentând lungimea maximă a unui subșir 2-crescător al celui de-al $i$-lea șir din cadrul celor $T$ șiruri date.

Restricții și precizări

• $1 \le T \le 10$
• $1 \le N_i \le 2\ 000$, pentru fiecare $i$, $1 \le i \le T$.
• Pentru $30\%$ din punctaj $1 \le N_i \le 400$, pentru fiecare $i$, $1 \le i \le T$.
• Pentru $60\%$ din punctaj $1 \le N_i \le 1\ 000$, pentru fiecare $i$, $1 \le i \le T$.
• Elementele din fiecare șir sunt numere naturale nenule din mulțimea $\{1, 2, 3, \dots, 30\ 000\}$.

Exemplu

s2c.in

2
8
1 1 3 2 5 3 4 5
5
9 6 4 2 7

s2c.out

6
3

Explicație

Avem $T = 2$ teste.

Primul șir are lungimea egală cu $8$. Subșirurile 2-crescătoare de lungime maximă, egală cu $6$, sunt:

• $1, 1, 3, 2, 5, 3$
• $1, 1, 3, 2, 5, 4$
• $1, 1, 3, 2, 5, 5$
• $1, 1, 3, 2, 4, 5$
• $1, 1, 2, 3, 4, 5$

Al doilea șir are lungimea $5$. Subșirurile 2-crescătoare de lungime maximă, egală cu $3$, sunt:

• $6, 4, 7$
• $6, 2, 7$
• $4, 2, 7$