هايدورا والأنابيب

المدخلات

السطر الأول يحتوي على عدد صحيح واحد $t$ ( $1 \leq t \leq 10000$ 1 \leq t \leq 10000): عدد حالات الاختبار.

السطر الأول من كل حالة اختبار يحتوي على عدد صحيح واحد $n$ $(1 \leq n \leq 2000)$ (1 \le n \le 2000) — طول المصفوفة $a$ .

السطر الثاني من كل حالة اختبار يحتوي على $n$ عدد صحيح مفصول $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$ .

يتم ضمان أن مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $2000$ .

المخرجات

لكل حالة اختبار، أخرج عدد صحيح واحد: الحد الأقصى لعدد الأنابيب التي يمكنك ربطها.

أمثلة

مثال 1

Loading

ملاحظة

في حالة الاختبار الأولى، يمكننا الحصول على الحد الأقصى لعدد الأنابيب التي يمكننا ربطها عن طريق الاتصال

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

في حالة الاختبار الثانية، يمكننا الحصول على الحد الأقصى لعدد الأنابيب التي يمكننا ربطها عن طريق الاتصال $Use Gnome Sort for this problem$

2 \mapsto 3 \mapsto 3

2 \mapsto 3 \mapsto 3

التقييم

المهمة الفرعية $1$ ( $20$ نقطة) : $(1 \leq a_{i} \leq 2)$ (1 \le a_i \le 2)
المهمة الفرعية $2$ ( $30$ نقطة) : لا قيود إضافية