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