Зала засідань ради директорів
Вас нещодавно найняли в інвестиційний фонд, але ви швидко помітили, що щось не так, особливо коли гроші клієнтів вкладалися в дві компанії, обрані за рекомендацією астролога.
На жаль, протягом останніх n днів ціни на акції переважно знижувалися. Бос скликав термінову нараду.
"Пані та панове, ви всі знаєте ситуацію. Які є ідеї?" - бос завжди вмів говорити прямо по суті (навіть якщо ця суть була в іншому вимірі реальності).
"Ми можемо вибрати підмножину днів, коли ціни тільки зростали, і показувати клієнту ціни компанії лише в ці дні!" - запропонував Біллі, останній співробітник місяця.
"Ми можемо досягти більшого! Оберіть дні так, щоб ціни обох компаній утворювали зростаючу послідовність!" - додала Анна, старший менеджер, не бажаючи залишатися осторонь.
"А як щодо того, щоб звільнити астролога і провести серйозне дослідження?" - ці слова вирвалися у вас майже мимоволі, ніби ваш мозок і голосові зв'язки діяли без вашої згоди.
Бос подивився на вас. Це було не зовсім схвалення...
Тепер у вас є синці, багато сходів для підйому і багато роботи. Враховуючи ціни акцій двох компаній протягом n послідовних днів, знайдіть максимальну підмножину днів, у які обидві цінові підпослідовності строго зростають. Достатньо вивести максимальну кількість днів.
Вхідні дані
Перша стрічка містить кількість тестів z. Перша стрічка кожного тесту містить кількість днів n (1 ≤ n ≤ 200 000). Далі йдуть два рядки. Перший рядок містить n натуральних чисел, що не перевищують 10^9 - ціни на акції першої компанії за всі n днів. Другий рядок - ціни на акції другої компанії, у тому ж форматі. Загальна кількість днів у всіх тестах не перевищує 2 000 000.
Вихідні дані
Для кожного тесту в окремому рядку виведіть одне ціле число - шукану максимально можливу кількість днів.