Мости для сигналів
'О ні, вони знову це зробили!' — вигукнув головний дизайнер заводу з виробництва чипів у Ваферляндії. Розробники маршрутів знову все заплутали, проклавши сигнали на чипі між портами двох функціональних блоків так, що вони всюди перетинаються. Це остання стадія випуску продукту, і вже занадто дорого виправляти маршрутизацію. Тому інженерам довелося створити для сигналів мости, використовуючи третій вимір, щоб жодні два сигнали не перетиналися. Створення мосту — складна операція, тому бажано провести у вигляді мостів якомога менше сигналів. Потрібна комп'ютерна програма для знаходження максимальної кількості сигналів, які можна з'єднати на кремнієвій пластині без перетинів. Пам'ятайте, що функціональний блок може мати тисячі сигнальних портів, тому для вирішення задачі необхідно написати програму. Ви готові до цього завдання?
Малюнок 1. Зліва: порти двох блоків реалізують відображення сигналів (4,2,6,3,1,5). Справа: не більше трьох сигналів можуть пересуватися по кремнієвій поверхні, не перетинаючись між собою. Сигнали, позначені пунктиром, повинні утворювати мости.
Типова ситуація зображена на малюнку 1. Порти двох функціональних блоків пронумеровані з 1 до p, зверху вниз. Відображення сигналів задається перестановкою чисел від 1 до p у вигляді списку з p унікальних чисел у проміжку від 1 до p, де i-е число вказує на номер порту справа, до якого приєднаний i-ий порт зліва. Два сигнали перетинаються, якщо перетинаються відрізки, що з'єднують їх відповідні порти.
Вхідні дані
Перша строка містить кількість тестів n. Кожен тест починається з рядка, що містить кількість портів p (p < 40000) на двох функціональних блоках. Далі слідують p рядків, що описують відображення сигналів: i-ий рядок містить номер порту в правій частині блоку, з'єднаного з i-им портом блоку в лівій частині.
Вихідні дані
Для кожного тесту виведіть в окремому рядку найбільшу кількість сигналів, які можуть бути передані по кремнієвій площині без перетинів.