Лавруша~--- добросовестный ученик, который мечтает стать программистом. На последнем уроке информатики его любимая учительница предложила ему решить такую задачу.

Лавруше дана последовательность натуральных чисел \(a_1,\ldots, a_n\). Ему нужно разделить последовательность чисел \(1,2,3, \ldots, n\) на две последовательности \(b_1, \ldots, b_m\) и \(c_1, \ldots, c_k\) таким образом, чтобы:

1. Каждое натуральное число \(1 \le r \le n\) было элементом ровно одной из последовательностей \(b\) или \(c\).

2. Для каждой пары индексов \(1 \le i, j \le m, i \ne j\) числа \(a_{b_i}\) и \(a_{b_j}\) были взаимно простыми. Взаимно простыми называются числа, наибольший общий делитель которых равен единице.

3. Для каждой пары индексов \(1 \le i, j \le k, i \ne j\) числа \(a_{c_i}\) и \(a_{c_j}\) были взаимно простыми.

Разбиение последовательности может быть неоднозначно. Поэтому учительница попросила Лаврушу найти такое разбиение, чтобы оно максимизировало количество элементов в последовательности \(b_i\). Если существует несколько разбиений, которые максимизируют количество элементов в последовательности \(b_i\), то нужно найти среди них такое, чтобы последовательность \(b_i\) была лексикографически наименьшей.

Будем говорить, что последовательность \(q_1, q_2, \ldots, q_W\) является лексикографически меньше последовательности \(p_1, p_2, \ldots, p_W\), если существует такое \(i\), что \(q_i < p_i\), а для произвольного \(j < i\) выполняется \(p_j = q_j\).

Напишите программу, которая для заданной последовательности чисел \(a\) найдет оптимальное разбиение последовательности цифр \(1,2,3, \ldots, n\) на две последовательности \(b_1, \ldots, b_m\) и \(c_1, \ldots, c_k\).