Экзамены Сакурако закончились, она справилась на отлично. В награду она получила перестановку \(p\). Косукэ был не совсем доволен, потому что он провалил один экзамен и не получил подарок. Он решил пробраться в её комнату (спасибо за код от её замка) и испортить перестановку так, чтобы она стала простой.
Перестановка \(p\) считается простой, если для каждого \(i\) \((1\le i \le n)\) выполняется одно из условий:
Например, перестановки \([1, 2, 3, 4]\), \([5, 2, 4, 3, 1]\) и \([2, 1]\) являются простыми, а \([2, 3, 1]\) и \([5, 2, 1, 4, 3]\) — нет.
За одну операцию Косукэ может выбрать индексы \(i,j\) \((1\le i,j\le n)\) и поменять местами элементы \(p_i\) и \(p_j\).
Сакурако вот-вот вернется домой. Ваша задача — вычислить минимальное количество операций, которые необходимо выполнить Косукэ, чтобы сделать перестановку простой.
Выходные данные
Для каждого набора входных данных выведите минимальное количество операций, которые необходимо выполнить Косукэ, чтобы перестановка стала простой.
Примечание
В первом и втором примерах перестановки уже простые.
В четвёртом примере достаточно поменять местами \(p_2\) и \(p_4\). Таким образом перестановка станет равна \([2, 1, 4, 3]\) за \(1\) операцию.