Саша очень любит читать книги. При прочтении одной книги он познакомился с необычным персонажем. Персонаж говорит про себя так: «У меня много имён в разных странах. Митрандир среди эльфов, Таркун среди гномов; в юности на давно забытом Западе я был Олорином, на юге — Инканус, на севере — Гэндальф, а на востоке я не бываю.»
И тут Саша задумался, а какое имя дали бы герою на Востоке? На Востоке все имена — палиндромы. Строка называется палиндромом, если она одинаково читается слева-направо и справа-налево. Например, строки «kazak», «oo» и «r» — палиндромы, а строки «abb» и «ij» — нет.
Саша считает, что героя назвали бы в честь одного из богов Востока. Так как имена не должны повторяться, на Востоке поступают следующим образом: записывают исходное имя как строку, из которой хотят получить новое имя на лист бумаги. Затем разрезают лист минимальное количество раз \(k\), получив при этом \(k+1\) лист с подстроками имени, и склеивают полученные куски в новую строку. Листы при этом нельзя переворачивать, их можно только менять местами.
Таким образом, выполнив \(3\) разреза в строке f|de|abc|g, может быть получена строка abcdefg (поменяв местами листы с подстроками f и abc), а строка cbadefg — нет.
Более формально, Саша хочет для данного палиндрома \(s\) найти такое минимальное \(k\), что существует способ разрезать исходную строку на \(k + 1\) подстроку, а затем склеить их так, чтобы полученная строка являлась палиндромом и была отлична от исходной строки \(s\). Если решения не существует, выведите «Impossible» (без кавычек).
Выходные данные
Выведите одно целое число \(k\) — минимальное число разрезов, необходимых для получения нового имени, или «Impossible» (без кавычек), если ответа не существует.
Примечание
В первом примере можно выполнить разрезы в следующих местах: no|l|on, а затем склеить их как on|l|no. Можно показать, что не существует решения, использующего один разрез.
Во втором примере строку можно разрезать посредине и поменять половины местами, получив строку toot.
В третьем примере все полученные палиндромы будут совпадать с исходной строкой.
В четвёртом примере можно отрезать суффикс nik и добавить его в начало, получив nikkinnikkin.