Вам задано цілочисельну матрицю розміру n \times 2.
Елементи першого стовпця матриці утворюють перестановку чисел n+1, n+2, \dots, 2n, а елементи другого стовпця — перестановку чисел 1, 2, \dots, n.
Ви можете виконати довільну кількість ходів. За один хід можна зробити таке.
Вибрати будь-яке додатне ціле число .
Вибрати послідовність із різних чисел (b_1, b_2, \dots, b_k), де 1 \le b_i \le 2n для всіх 1 \le i \le k.
Виконати циклічний зсув усіх вибраних чисел у матриці (число b_1 переходить на місце числа b_2, число b_2 — на місце числа b_3, …, число b_k — на місце числа b_1).
Заплатити монет.
Яку мінімальну кількість монет потрібно заплатити, щоб у кожному рядку лівий елемент став меншим за правий?
Зауважте, що мінімізувати кількість ходів не потрібно.
У першому рядку задано ціле число — кількість наборів вхідних даних.
У першому рядку кожного набору вхідних даних задано ціле число — кількість рядків матриці .
У наступних рядках кожного набору вхідних даних задано по два цілі числа a_{i,1} та a_{i,2} — елементи матриці.
1 \le t \le 10^6,
1 \le n \le 10^6,
сума всіх значень за всіма наборами вхідних даних не перевищує 10^6.
Для кожного набору вхідних даних виведіть відповідь у такому форматі.
У першому рядку виведіть мінімальну кількість монет.
У другому рядку виведіть ціле число — кількість ходів.
У наступних рядках виведіть ходи у форматі k\ b_1\ b_2\ b_3 \dots b_k.
Приклад
У першому прикладі задано матрицю
Однією з оптимальних стратегій для цієї матриці є виконання одного ходу, вибравши k = 4 та послідовність b = (1, 7, 2, 8). Під час цього ходу
число переходить на місце числа ,
число переходить на місце числа ,
число переходить на місце числа ,
число переходить на місце числа .
Після цього ходу матриця набуває вигляду
Тепер у кожному рядку лівий елемент менший за правий.
Загальна кількість сплачених монет дорівнює чотирьом.