После мистического исчезнования Ashish, каждый из его любимых учеников Ishika и Hriday, получил одну половину секретного сообщения. Эти сообщения могут быть описаны перестановками размера \(n\). Назовем их \(a\) и \(b\).
Напомним, что перестановка из \(n\) элементов это последовательность чисел \(a_1, a_2, \ldots, a_n\), в которой каждое число от \(1\) до \(n\) встречается ровно один раз.
Сообщение может быть расшифровано из конфигурации перестановок \(a\) и \(b\), в котором количество совпадающих пар элементов максимально. Пара элементов \(a_i\) и \(b_j\) называется совпадающей, если:
- \(i = j\), таким образом, у них один и тот же индекс.
- \(a_i = b_j\)
Его ученикам разрешается совершать следующую операцию произвольное число раз:
- выбрать число \(k\) и циклически сдвинуть одну из перестановок влево или вправо \(k\) раз.
Циклический сдвиг перестановки \(c\) влево это операция, которая присваивает \(c_1:=c_2, c_2:=c_3, \ldots, c_n:=c_1\) одновременно. Аналогично, циклический сдвиг перестановки \(c\) вправо это операция, которая присваивает \(c_1:=c_n, c_2:=c_1, \ldots, c_n:=c_{n-1}\) одновременно.
Помогите Ishika и Hriday найти наибольшее возможное число совпадающих пар в данных перестановках после применения описанных операций несколько (возможно, ноль) раз.
Выходные данные
Выведите наибольшее возможное число совпадающих пар в данных перестановках после применения описанных операций несколько (возможно, ноль) раз.
Примечание
В первом примере можно сдвинуть \(b\) направо на \(k = 1\). Получившиеся перестановки будут \(\{1, 2, 3, 4, 5\}\) и \(\{1, 2, 3, 4, 5\}\).
Во втором примере не требуется совершать никаких операций. По всем возможным сдвигам \(a\) и \(b\), число совпадающих пар не будет превышать \(1\).
В третьем примере можно сдвинуть \(b\) влево на \(k = 1\). Получившиеся перестановки будут \(\{1, 3, 2, 4\}\) и \(\{2, 3, 1, 4\}\). Позиции \(2\) и \(4\) будут являться совпадающей парой. По всем возможным циклическим сдвигам \(a\) и \(b\), количество совпадающих пар не будет превышать \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 4 5
2 3 4 5 1
|
5
|
|
2
|
5
5 4 3 2 1
1 2 3 4 5
|
1
|
|
3
|
4
1 3 2 4
4 2 3 1
|
2
|