Haidora və borular

Giriş

Birinci sətirdə tək bir tam ədəd $t$ ( $1 \leq t \leq 10000$ 1 \leq t \leq 10000): test hallarının sayı.

Hər bir test halının birinci sətirində tək bir tam ədəd $n$ $(1 \leq n \leq 2000)$ (1 \le n \le 2000) — $a$ massivinin uzunluğu.

Hər bir test halının ikinci sətirində $n$ ayrılmış tam ədəd $a_{1}, a_{2}, .., a_{n}$ a_1,a_2,..,a_n $(1 \leq a_{1}, a_{2}, .., a_{n} \leq 1 0^{9})$ (1 \le a_1,a_2,..,a_n \le 10^9) — $a$ massivi.

Bütün test hallarının $n$ cəminin 2000-dən çox olmayacağına zəmanət verilir.

Çıxış

Hər bir test halı üçün bir tam ədəd çap edin: birləşdirə biləcəyiniz maksimum boru sayı.

Nümunələr

Nümunə 1

Loading

Qeyd

Birinci test halında, birləşdirə biləcəyimiz maksimum boru sayını əldə edə bilərik

1 \mapsto 2 \mapsto 2 \mapsto 3 \mapsto 4 \mapsto 5 \mapsto 6

1 \mapsto 2 \mapsto 2 \mapsto 3 \mapsto 4 \mapsto 5 \mapsto 6

İkinci test halında, birləşdirə biləcəyimiz maksimum boru sayını əldə edə bilərik $Use Gnome Sort for this problem$

2 \mapsto 3 \mapsto 3

2 \mapsto 3 \mapsto 3

Bal hesablama

Alt tapşırıq $1$ ( $20$ xal) : $(1 \leq a_{i} \leq 2)$ (1 \le a_i \le 2)
Alt tapşırıq $2$ ( $30$ xal) : Əlavə məhdudiyyət yoxdur