Заданы \(n\) перестановок \(a_1, a_2, \dots, a_n\), каждая длины \(m\). Напомним, что перестановка длины \(m\) — это последовательность из \(m\) различных целых чисел от \(1\) до \(m\).
Назовем красотой перестановки \(p_1, p_2, \dots, p_m\) наибольшее такое \(k\), что \(p_1 = 1, p_2 = 2, \dots, p_k = k\). Если \(p_1 \neq 1\), то красота равна \(0\).
Произведение двух перестановок \(p \cdot q\) — это такая перестановка \(r\), что \(r_j = q_{p_j}\).
Для каждого \(i\) от \(1\) до \(n\) выведите наибольшую красоту перестановки \(a_i \cdot a_j\) по всем \(j\) от \(1\) до \(n\) (возможно, \(i = j\)).