Reading books is one of Sasha's passions. Once while he was reading one book, he became acquainted with an unusual character. The character told about himself like that: "Many are my names in many countries. Mithrandir among the Elves, Tharkûn to the Dwarves, Olórin I was in my youth in the West that is forgotten, in the South Incánus, in the North Gandalf; to the East I go not."

And at that moment Sasha thought, how would that character be called in the East? In the East all names are palindromes. A string is a palindrome if it reads the same backward as forward. For example, such strings as "kazak", "oo" and "r" are palindromes, but strings "abb" and "ij" are not. 

Sasha believed that the hero would be named after one of the gods of the East. As long as there couldn't be two equal names, so in the East people did the following: they wrote the original name as a string on a piece of paper, then cut the paper minimum number of times $k$, so they got $k+1$ pieces of paper with substrings of the initial string, and then unite those pieces together to get a new string. Pieces couldn't be turned over, they could be shuffled.

In this way, it's possible to achive a string abcdefg from the string f|de|abc|g using $3$ cuts (by swapping papers with substrings f and abc). The string cbadefg can't be received using the same cuts.

More formally, Sasha wants for the given palindrome $s$ find such minimum $k$, that you can cut this string into $k + 1$ parts, and then unite them in such a way that the final string will be a palindrome and it won't be equal to the initial string $s$. It there is no answer, then print "Impossible" (without quotes).


-----Input-----

The first line contains one string $s$ ($1 \le |s| \le 5\,000$) — the initial name, which consists only of lowercase Latin letters. It is guaranteed that $s$ is a palindrome.


-----Output-----

Print one integer $k$ — the minimum number of cuts needed to get a new name, or "Impossible" (without quotes).


-----Examples-----
Input
nolon

Output
2

Input
otto

Output
1

Input
qqqq

Output
Impossible

Input
kinnikkinnik

Output
1



-----Note-----

In the first example, you can cut the string in those positions: no|l|on, and then unite them as follows on|l|no. It can be shown that there is no solution with one cut.

In the second example, you can cut the string right in the middle, and swap peaces, so you get toot.

In the third example, you can't make a string, that won't be equal to the initial one.

In the fourth example, you can cut the suffix nik and add it to the beginning, so you get nikkinnikkin.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Constructive algorithms

Starter code:

Solutions:
import sys
s = input()
n = len(s)
for i in range(n):
	t = s[i:] + s[:i]
	if t != s and t == t[::-1]:
		print(1)
		sys.exit(0)
if s[:n // 2] != s[n - n // 2:]:
	print(2)
	sys.exit(0)
is4 = True
for i in range(n):
	if not (n % 2 == 1 and i == n // 2):
		if s[i] != s[0]:
			is4 = False
if is4 == False:
	print(2)
else:
	print('Impossible')


import sys
s = input().rstrip()
n = len(s)
same = True
s1 = s[:n // 2]
for i in range(len(s1) - 1):
	if s1[i] != s1[i + 1]:
		same = False
if same:
	print('Impossible')
	exit()
for i in range(1, n):
	t = s[i:] + s[:i]
	flag = True
	for i in range(n // 2):
		if t[i] != t[n - 1 - i]:
			flag = False
	if flag and t != s:
		print(1)
		exit()
print(2)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def toord(c):
	return ord(c) - ord('a')

def lcm(a, b):
	return a * b // lcm(a, b)
mod = 998244353
INF = float('inf')
from math import factorial, sqrt, ceil, floor, gcd
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	s = input()
	le = len(s)
	for i in range(1, le // 2):
		if s[i] != s[i - 1]:
			for j in range(1, le - 1):
				now = s[j:] + s[:j]
				if now == now[::-1] and now != s:
					print(1)
					break
			else:
				print(2)
			break
	else:
		print('Impossible')
main()


s = input()
N = len(s)
if len(set(list(s))) == 1:
	print('Impossible')
else:
	if len(set(list(s))) == 2:
		t = list(set(list(s)))
		(k1, k2) = (t[0], t[1])
		if s.count(k1) == N - 1 or s.count(k2) == N - 1:
			print('Impossible')
			exit()
	t = s
	for i in range(N):
		t = t[1:] + t[0]
		if t != s and t[::-1] == t:
			print(1)
			exit()
	print(2)


import sys
from math import *
from fractions import gcd
readints = lambda : map(int, input().strip('\n').split())

def ispal(s):
	n = len(s)
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			return False
	return True
s = input()
n = len(s)
for i in range(1, n):
	(a, b) = (s[:i], s[i:])
	t = b + a
	if t != s and ispal(t):
		print(1)
		sys.exit(0)
k = n / 2
if n % 2 == 1:
	k = ceil(k)
k = int(k)
for i in range(1, k):
	(a, b, c) = (s[:i], s[i:-i], s[-i:])
	t = c + b + a
	if t != s and ispal(t):
		print(2)
		sys.exit(0)
print('Impossible')


import sys
import math
from collections import defaultdict

def is_pal(s):
	(i, j) = (0, len(s) - 1)
	while i <= j:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True
s = sys.stdin.readline()[:-1]
n = len(s)
if n % 2 == 0:
	z = True
	for i in range(n // 2 - 1):
		if s[i] != s[i + 1]:
			z = False
			break
	if z:
		print('Impossible')
	else:
		for i in range(n // 2):
			if is_pal(s[i + 1:] + s[:i + 1]) and s[i + 1:] + s[:i + 1] != s:
				print(1)
				return
		print(2)
else:
	z = True
	for i in range(n // 2 - 1):
		if s[i] != s[i + 1]:
			z = False
			break
	if z:
		print('Impossible')
	else:
		print(2)


s = input()
ans = 'Impossible'
n = len(s)
for i in range(1, n - 1):
	t = s[i:] + s[:i]
	if t != s and t == t[::-1]:
		ans = '1'
		break
if len(ans) != 1:
	(l, r) = (1, n - 1)
	while l <= r:
		t = s[r:] + s[l:r] + s[:l]
		if t != s and t == t[::-1]:
			ans = '2'
			break
		l += 1
		r -= 1
print(ans)


from collections import Counter

def solve(s):
	n = len(s)
	c = Counter(s)
	if max(c.values()) >= n - 1:
		return 'Impossible'
	for i in range(1, n):
		new_s = s[i:] + s[:i]
		if new_s == s:
			continue
		for j in range(n // 2 + 1):
			if new_s[j] != new_s[-j - 1]:
				break
		else:
			return 1
	return 2
s = input()
print(solve(s))


s = input()
if len(set(s[:len(s) // 2])) <= 1:
	print('Impossible')
	exit()
if len(s) % 2 == 0:
	for i in range(1, len(s)):
		n = s[i:] + s[:i]
		if n == n[::-1] and n != s:
			print(1)
			exit()
print(2)


text = input()
flag = True
if len(text) % 2 == 0:
	smb = text[0]
	for i in text:
		if i != smb:
			flag = False
			break
else:
	smb = text[0]
	for i in range(len(text) // 2):
		if text[i] != smb:
			flag = False
			break
if flag:
	print('Impossible')
else:
	k = len(text)
	for i in range(1, (k + 1) // 2 + 1):
		flag = True
		string = text[i:] + text[:i]
		for j in range((k + 1) // 2):
			if string[j] != string[-j - 1]:
				flag = False
				break
		if flag and string != text:
			break
		else:
			flag = False
	if flag:
		print(1)
	else:
		print(2)


def main():
	s = input()
	n = len(s)
	for part in range(n - 1):
		newstr = s[part + 1:] + s[:part + 1]
		if newstr != s and newstr == newstr[::-1]:
			print(1)
			return
	left = s[:n // 2]
	right = s[(n + 1) // 2:]
	if n == 1 or (left == right and len({c for c in left}) == 1):
		print('Impossible')
	else:
		print(2)
main()


import sys
s = input()
flag = 0
for i in range(1, len(s) // 2):
	if s[i] != s[i - 1]:
		flag = 1
		break
if flag == 0:
	print('Impossible')
	sys.exit()
elif len(s) % 2 == 0:
	flag = 0
	curr = len(s)
	while curr % 2 == 0:
		for i in range(curr // 2):
			if s[i] != s[curr // 2 - 1 - i]:
				flag = 1
		if flag:
			break
		curr = curr // 2
	if flag:
		print(1)
	else:
		print(2)
else:
	print(2)


def pal(s):
	s = list(s)
	s1 = s[:len(s) // 2]
	if len(s) % 2 == 0:
		s2 = s[len(s) // 2:]
	else:
		s2 = s[len(s) // 2 + 1:]
	s2.reverse()
	if s1 == s2:
		return True
	return False
s = input()
prev = s[0]
for item in s:
	if item != prev:
		break
	prev = item
else:
	print('Impossible')
	exit()
for i in range(1, len(s) // 2):
	if pal(s[i:] + s[:i]) == True and s[i:] + s[:i] != s:
		print(1)
		break
else:
	for i in range(len(s) // 2 - 1, -1, -1):
		if pal(s[:i + 1]) == False:
			if len(s) % 2 == 1:
				print(2)
			elif i == len(s) // 2 - 1:
				print(1)
			else:
				print(2)
			break
	else:
		print('Impossible')


import collections
import heapq
import bisect
import math
import time

class Solution2:

	def solve(self, A1, A2):
		pass

def gcd(a, b):
	if not b:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return b * a // gcd(b, a)

class Solution:

	def solve(self, s):
		count = collections.Counter(s)
		if len(count) == 1:
			return 'Impossible'
		if len(count) == 2:
			if any((v == 1 for v in count.values())):
				return 'Impossible'
		for i in range(len(s)):
			(k1, k2) = (s[i:], s[:i])
			new_s = k1 + k2
			if new_s[::-1] == new_s and new_s != s:
				return '1'
		return '2'
sol = Solution()
sol2 = Solution2()
for test_case in range(1):
	N = input()
	out = sol.solve(N)
	print(out)


from collections import Counter
s = input()
l = len(s)
c = Counter(s)
if l < 4:
	print('Impossible')
	exit()
elif len(set(s)) == 1:
	print('Impossible')
	exit()
elif l % 2 == 1 and max(c.values()) == l - 1:
	print('Impossible')
	exit()
s1 = s[:]
for i in range(l):
	a = s[i:] + s[:i]
	if a != s and a == a[::-1]:
		print(1)
		exit()
print(2)


import sys
from collections import Counter
S = input()
N = len(S)
C = Counter(S)
if len(C) == 1:
	print('Impossible')
	sys.exit()
if len(C) == 2:
	if min(list(C.values())) == 1:
		print('Impossible')
		sys.exit()
for i in range(1, N):
	T = S[i:] + S[:i]
	if T == T[::-1] and T != S:
		print(1)
		sys.exit()
print(2)


s = input().strip()
n = len(s)
for i in s:
	if s.count(i) >= n - 1:
		print('Impossible')
		break
else:
	for i in range(n // 2):
		p = s[i + 1:] + s[:i + 1]
		if p == p[::-1] and p != s:
			print(1)
			break
	else:
		print(2)


def one():
	global s
	for i in range(1, len(s) - 1):
		tmp = s[i:] + s[:i]
		if tmp == tmp[::-1] and tmp != s:
			return True
	return False

def two():
	global s
	for i in range(1, (len(s) + 1) // 2):
		tmp = s[-i:] + s[i:-i] + s[:i]
		if tmp == tmp[::-1] and tmp != s:
			return True
	return False
s = input()
if one():
	print(1)
elif two():
	print(2)
else:
	print('Impossible')


def solve(s):
	n = len(s)
	for i in range(n):
		s2 = s[i:] + s[:i]
		if s != s2 and s2[::-1] == s2:
			return 1
	for i in range(n // 2 + 1, n):
		if s[i] != s[0]:
			return 2
	return 'Impossible'
s = input()
print(solve(s))


s = input()
n = len(s)

def check(name):
	return name == name[::-1] and name != s
for i in range(1, n):
	new_name = s[i:] + s[:i]
	if check(new_name):
		print(1)
		exit()
for i in range(1, n // 2 + 1):
	new_name = s[-i:] + s[i:-i] + s[:i]
	if check(new_name):
		print(2)
		exit()
print('Impossible')


s = input()
l = len(s)
c = s[0]
diff = False
for i in range(0, int(l / 2)):
	if s[i] != c:
		diff = True
if not diff:
	print('Impossible')
	exit()
s_2 = s + s
for i in range(1, l):
	is_palendrome = True
	for j in range(int(l / 2)):
		if s_2[j + i] != s_2[i + l - j - 1]:
			is_palendrome = False
	if is_palendrome and s_2[i:i + l] != s:
		print(1)
		exit()
print(2)


s = input()
d = dict()
for i in s:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
flag = 0
if len(set(s)) == 1:
	print('Impossible')
	flag = 1
elif len(d) == 2:
	for i in d.values():
		if i == 1:
			print('Impossible')
			flag = 1
if flag == 0:
	n = len(s)
	if n % 2 != 0:
		print(2)
	elif s[:n // 2] == s[n // 2:]:
		t = s[:n // 2]
		n1 = n // 2
		while t[:n1 // 2] == t[n1 // 2:] and n1 % 2 == 0:
			t = t[:n1 // 2]
			n1 = n1 // 2
		if n1 % 2 == 0:
			print(1)
		else:
			print(2)
	else:
		print(1)


s = input()
if len(s) < 3:
	print('Impossible')
	exit()
d = {}
for i in s:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
mm = 0
for (key, value) in d.items():
	mm = max(mm, value)
if mm >= len(s) - 1:
	print('Impossible')
	exit()
if len(s) % 2 == 1:
	print(2)
	exit()
else:
	xx = s
	while True:
		if len(xx) % 2 == 1:
			print(2)
			exit()
		ll = xx[0:len(xx) // 2]
		rr = xx[len(xx) // 2:]
		if ll != rr:
			print(1)
			exit()
		xx = ll


def isPalindrome(s):
	return s == s[::-1]
s = input()
r = 0
for i in set(s):
	r = max(r, s.count(i))
if len(set(s)) == 1 or len(s) <= 3:
	print('Impossible')
elif r >= len(s) - 1:
	print('Impossible')
else:
	fl = 0
	for i in range(len(s)):
		e = s[0:i]
		f = s[i:]
		e = f + e
		if isPalindrome(e) and e != s:
			fl = 1
			print(1)
			break
	if fl == 0:
		print(2)


from collections import Counter
import sys
S = input()
L = len(S)

def pand(x):
	if x == x[::-1]:
		return True
	else:
		return False
for i in range(1, len(S)):
	if S[i:] + S[:i] != S and pand(S[i:] + S[:i]) == True:
		print(1)
		sys.exit()
if len(Counter(S).keys()) == 1:
	print('Impossible')
	sys.exit()
if L % 2 == 0:
	print(2)
else:
	for i in range(1, L // 2 + 1):
		if S[:i] != S[-i:]:
			print(2)
			sys.exit()
	else:
		print('Impossible')


s = input()
if len(s) == 1:
	print('Impossible')
elif len(s) < 4:
	print('Impossible')
elif s.count(s[0]) == len(s) - 1:
	print('Impossible')
else:
	tf = True
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			tf = False
			break
	if tf:
		print('Impossible')
	else:
		ans = 2
		for i in range(1, len(s)):
			a = s[i:] + s[:i]
			if a != s and a == a[::-1]:
				ans = 1
				break
		print(ans)


s = input()
n = len(s)
if n <= 2:
	print('Impossible')
	return
if len(s) % 2 == 1:
	s = s[:n // 2] + s[n // 2 + 1:]
	if len(set(s)) == 1:
		print('Impossible')
		return
	print(2)
	return
if len(set(s)) == 1:
	print('Impossible')
	return
for i in range(0, n):
	cut = s[:i]
	orig = s[i:]
	pal = orig + cut
	if pal == pal[::-1] and pal != s:
		print(1)
		return
print(2)
return


def isPal(x):
	for i in range(len(x) // 2):
		if x[i] != x[len(x) - 1 - i]:
			return False
	return True
s = list(input())
f = {}
for c in s:
	if c in f:
		f[c] += 1
	else:
		f[c] = 1
if len(f) == 1:
	print('Impossible')
	return
elif len(f) == 2:
	if 1 in f.values():
		print('Impossible')
		return
if len(s) % 2 == 0:
	for i in range(1, len(s)):
		new = s[i:] + s[:i]
		if s != new:
			if isPal(new):
				print(1)
				return
print(2)


import sys
string = input()
n = len(string)
c = string[0]
if all((c == string[i] for i in range(n // 2))) and all((c == string[i] for i in range((n + 1) // 2, n))):
	print('Impossible')
	return
for i in range(1, n):
	part = string[i:] + string[:i]
	if part == part[::-1] and part != string:
		print(1)
		return
print(2)


def solve():
	initial_name = input().strip()
	for ch in initial_name[:2]:
		if initial_name.count(ch) >= len(initial_name) - 1:
			return 'Impossible'
	for cut_point in range(1, len(initial_name)):
		new_name = initial_name[cut_point:] + initial_name[:cut_point]
		if new_name != initial_name and list(new_name) == list(reversed(new_name)):
			return 1
	return 2
print(solve())


from math import floor
string = input().strip()
count = 1
for i in range(1, len(string)):
	if string[i] == string[-1]:
		count += 1
	else:
		count -= 1
if count == len(string) or count == len(string) - 2:
	print('Impossible')
else:
	one = False
	for i in range(floor(len(string) / 2)):
		new_string = string[i + 1:] + string[:i + 1]
		if string != new_string and new_string == new_string[::-1]:
			one = True
			print(1)
			break
	if not one:
		print(2)


def chk():
	global s
	cnt = 0
	for i in range(len(s)):
		if s[i] != s[0]:
			cnt += 1
	return cnt < 2

def i_p(s):
	for i in range(len(s) // 2):
		if s[i] != s[-(i + 1)]:
			return False
	return True
s = input()
if chk():
	print('Impossible')
	exit()
for i in range(len(s)):
	if i_p(s[i:] + s[:i]) and s[i:] + s[:i] != s:
		print(1)
		exit()
print(2)


from sys import *
s = input()

def check(t):
	return t == t[::-1] and t != s
for i in range(1, len(s)):
	t = s[i:] + s[:i]
	if check(t):
		print('1')
		exit()
for i in range(1, len(s) // 2 + len(s) % 2):
	t = s[-i:] + s[i:-i] + s[:i]
	if check(t):
		print('2')
		exit()
print('Impossible')


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(50001)]
pp = []

def SieveOfEratosthenes(n=50000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(50001):
		if prime[i]:
			pp.append(i)

def palindrome(s):
	n = len(s)
	for i in range((n + 1) // 2):
		if s[i] != s[n - 1 - i]:
			return False
	return True
s = list(input())
n = len(s)
if len(set(s)) == 1 or n == 3:
	print('Impossible')
else:
	ch = 0
	for i in range(1, n):
		t = s[i:] + s[:i]
		if s != t and palindrome(t):
			ch = 1
			break
	if ch:
		print(1)
	else:
		ind = n
		for i in range(1, n):
			if s[i] != s[0]:
				ind = i
				break
		if ind < n // 2:
			print(2)
		else:
			print('Impossible')


from collections import Counter
n = input()
if len(Counter(n)) == 1 or len(Counter(n[:len(n) // 2] + n[len(n) // 2 + 1:])) == 1:
	print('Impossible')
	return
for i in range(1, len(n)):
	s1 = n[:i]
	s2 = n[i:]
	s3 = s2 + s1
	if s3[len(n) // 2:] == s3[:-len(n) // 2][::-1] and s3 != n:
		print(1)
		return
print(2)


s = input()
if len(s) == 1:
	print('Impossible')
	exit()
n = len(s)
m = len(s) // 2

def is_pal(s):
	n = len(s)
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			return False
	return True
for i in range(n):
	ns = s[i:] + s[:i]
	if n % 2 == 0:
		if is_pal(ns):
			if ns != s:
				print(1)
				exit()
	elif is_pal(ns):
		if ns != s:
			print(1)
			exit()
if len(s) % 2 == 0:
	if s[:m] != s[m:]:
		print(1)
		exit()
	else:
		if len(set(s[:m])) == 1:
			print('Impossible')
			exit()
		print(2)
		exit()
elif s[:m] != s[m + 1:]:
	print(2)
	exit()
else:
	if len(set(s[:m])) == 1:
		print('Impossible')
		exit()
	print(2)
	exit()


st = input()
flag = False
le = len(st)
for i in range(1, le // 2):
	if st[i] != st[i - 1]:
		flag = True
		break
if not flag:
	print('Impossible')
else:
	l = len(st)
	flag = 0
	for i in range(l):
		flag = 0
		rt = st[i:] + st[:i]
		if rt == rt[::-1] and st != rt:
			flag = 1
			break
	if flag == 1:
		print(1)
	else:
		print(2)


import sys
from collections import deque
import math
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
s = ip()
l = len(s)
for i in range(1, l - 1):
	x = s[i:] + s[:i]
	if x == x[::-1] and s != x:
		print(1)
		exit(0)
for j in range(1, l // 2 + l % 2):
	x = s[-j:] + s[j:-j] + s[:j]
	if x == x[::-1] and x != s:
		print(2)
		exit(0)
print('Impossible')


s = str(input())
n = len(s)
if (s.count(s[0]) == n) | (s.count(s[0]) == n - 1):
	print('Impossible')
else:
	ans = 2
	for i in range(n - 1):
		s1 = s[:i + 1]
		s2 = s[i + 1:]
		s3 = s2 + s1
		k = n // 2
		if s3[:k] == s3[:n - k - 1:-1] and s3 != s:
			ans = 1
	print(ans)


def checkPali(s):
	for i in range(len(s)):
		if s[i] != s[len(s) - i - 1]:
			return False
	return True

def check(s):
	for i in range(len(s)):
		s2 = s[i:] + s[:i]
		if checkPali(s2) and s != s2:
			return i

def checkOdd(s):
	for i in range(1, len(s) // 2):
		if s[i] != s[i - 1]:
			return False
	return True
s = input()
flag = True
if len(s) == 1:
	flag = True
elif len(s) % 2 != 0 and checkOdd(s):
	flag = True
else:
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			flag = False
if flag:
	print('Impossible')
elif check(s):
	print(1)
else:
	print(2)


def pallin(s):
	n = len(s)
	for i in range(0, n // 2):
		if s[i] != s[n - i - 1]:
			return False
	return True

def __starting_point():
	s = input()
	n = len(s)
	for i in range(n - 1, 0, -1):
		s1 = s[0:i]
		s2 = s[i:]
		t = s2 + s1
		if s != t and pallin(t):
			print('1')
			return
	for i in range(1, n // 2):
		if s[i] != s[i - 1]:
			print('2')
			return
	print('Impossible')
__starting_point()


import sys
import math

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def reverse(s):
	return s[::-1]

def isPalindrome(s):
	rev = reverse(s)
	if s == rev:
		return True
	return False
s = read_line()
n = len(s)
d = {}
for i in s:
	if i not in d:
		d[i] = 1
	else:
		d[i] += 1
f = True
if n & 1 == 1 and len(list(d.keys())) <= 2:
	if len(list(d.keys())) == 1:
		f = False
	elif 1 in list(d.values()):
		f = False
elif n & 1 != 1 and len(list(d.keys())) == 1:
	f = False
ans = 2
for i in range(1, n):
	pre = s[:i]
	post = s[i:]
	if isPalindrome(post + pre):
		if post + pre != s:
			ans = 1
			break
if f:
	print(ans)
else:
	print('Impossible')


s = input()
n = len(s)
from collections import Counter
c = Counter(s)
if len(set(s)) == 1:
	print('Impossible')
	exit()
if len(s) & 1 and max(c.values()) == n - 1:
	print('Impossible')
	exit()
s1 = s[:]
for i in range(n):
	s1 = s[i:] + s[:i]
	if s1 != s and s1 == s1[::-1]:
		print(1)
		exit()
print(2)


def is_palindrome(S):
	a = S[::-1]
	return S == a
s = input()
if len(s) == 1:
	print('Impossible')
	exit(0)
hop = 0
if len(s) % 2:
	if len(set(s[:len(s) // 2])) == 1:
		print('Impossible')
	else:
		print(2)
elif len(set(s)) == 1:
	print('Impossible')
elif s[:len(s) // 2] != s[len(s) // 2:]:
	print(1)
else:
	fl = 2
	while len(s) % 2 == 0:
		s = s[:len(s) // 2]
		if len(s) % 2 == 0 and (not is_palindrome(s[:len(s) // 2])):
			fl = 1
			break
	print(fl)


import os, sys
from io import BytesIO, IOBase

def ispalin(x):
	return x == x[::-1]

def main():
	s = input().strip()
	(n, an, ans) = (len(s), [], 3)
	for i in range(n // 2):
		an.append(s[i])
		if not ispalin(an):
			if n & 1:
				ans = 2
				break
			else:
				ans = 1 + (i != n // 2 - 1)
	if ans == 1:
		print(1)
	elif ans == 3:
		print('Impossible')
	else:
		for i in range(1, n - 1):
			z = s[i:] + s[:i]
			if ispalin(z) and z != s:
				print(1)
				break
		else:
			print(2)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


s = input()
hai = False
if len(s) % 2 == 0:
	for i in range(1, len(s)):
		s1 = s[i:] + s[:i]
		if s1 != s and s1 == s1[::-1]:
			print(1)
			exit()
	cur = len(s) // 2
	cur2 = cur
	cur -= 1
	while cur > 0:
		if s[:cur + 1] != s[cur2:]:
			print(2)
			exit()
		cur -= 1
		cur2 += 1
	print('Impossible')
else:
	cur = len(s) // 2
	cur2 = cur + 1
	cur -= 1
	while cur > 0:
		if s[:cur + 1] != s[cur2:]:
			print(2)
			exit()
		cur -= 1
		cur2 += 1
	print('Impossible')


from collections import defaultdict as dd
import math

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))

def ispal(s):
	for i in range(len(s) // 2):
		if not s[i] == s[-i - 1]:
			return False
	return True
s = li()
if len(s) % 2 == 0:
	bad = 1
	for i in range(1, len(s) // 2):
		if not s[i] == s[i - 1]:
			bad = 0
	if bad == 1:
		print('Impossible')
	else:
		seg = s
		while ispal(seg[0:len(seg) // 2]):
			if len(seg) // 2 % 2 == 1:
				print(2)
				bad = 1
				break
			seg = seg[0:len(seg) // 2]
		if bad == 1:
			pass
		else:
			print(1)
if len(s) % 2 == 1:
	bad = 1
	for i in range(1, len(s) // 2):
		if not s[i] == s[i - 1]:
			bad = 0
	if bad == 1:
		print('Impossible')
	else:
		print(2)


def isPalindrome(word):
	return True if word == word[::-1] else False
word = input()
n = len(word)
possible = False
for i in range(n // 2 + 1):
	new = word[i:] + word[:i]
	if isPalindrome(new) and new != word:
		possible = True
		print(1)
		break
if not possible:
	for i in range(1, n // 2 if n % 2 == 0 else (n + 1) // 2):
		if word[:i] != word[-i:]:
			possible = True
			print(2)
			break
if not possible:
	print('Impossible')


import math
st = input()

def pal(st, mark):
	bo = st == st[::-1]
	nst = ''
	if len(st) == 1:
		return mark
	if bo and len(st) % 2 == 1:
		nst = st[len(st) // 2 + 1:]
		mark = False
	elif bo:
		nst = st[len(st) // 2:]
	if nst == nst[::-1]:
		return pal(nst, mark)
	else:
		return mark
boo = pal(st, True)
if st[:len(st) // 2] == st[0] * (len(st) // 2) and st[math.ceil(len(st) / 2):] == st[0] * (len(st) // 2):
	print('Impossible')
elif len(st) % 2 == 0 and boo:
	print(1)
else:
	print(2)


s = input()
n = len(s) // 2
k = len(s)
allsame = True
for i in range(n):
	if s[i] != s[0]:
		allsame = False
if allsame:
	print('Impossible')
else:
	ans = False
	for i in range(1, n + 1):
		str = s[i:] + s[:i]
		if str[:n] == ''.join(reversed(str[k - n:])) and str != s:
			print(1)
			ans = True
			break
	if not ans:
		print(2)


def reverse(s):
	return s[::-1]

def isPalindrome(s):
	rev = reverse(s)
	if s == rev:
		return True
	return False
s = input()
n = len(s)
a = s[0]
if n % 2 == 0:
	same = True
	for i in range(n):
		if not a == s[i]:
			same = False
else:
	same = True
	for i in range(n):
		if not a == s[i] and (not i == n // 2):
			same = False
if not same:
	possible = False
	for i in range(1, n):
		next = s[i:] + s[:i]
		if not possible:
			possible = isPalindrome(next) and (not next == s)
	if possible:
		print(1)
	else:
		print(2)
else:
	print('Impossible')


s = input()
lz = len(s)
found = 0
ans = -1
for i in range(0, lz // 2):
	k = s[0:i + 1]
	if k != k[::-1]:
		found = 1
		ans = 2
for i in range(0, lz - 1):
	k = s[i + 1:lz] + s[0:i + 1]
	if k == k[::-1] and k != s:
		found = 1
		ans = 1
if not found:
	print('Impossible')
else:
	print(ans)


s = input()
n = len(s)

def check(s):
	return s == s[::-1]
ans = 10
if len(set(s)) == 1 or (len(s) & 1 and len(set(s)) == 2 and (s.count(sorted(list(set(s)))[0]) == n - 1 or s.count(sorted(list(set(s)))[0]) == 1)):
	print('Impossible')
else:
	for i in range(n):
		suf = s[-i - 1:]
		pref = s[:-i - 1]
		newstr = suf + pref
		if check(newstr) and newstr != s:
			ans = min(ans, 1)
	print(int(str(ans), 2))


def isPalindrom(s, n):
	for i in range(n // 2):
		if s[i] != s[n - 1 - i]:
			return False
	return True

def solve(s):
	if len(s) % 2 == 0:
		temp = s[0] * len(s)
		if s == temp:
			return 'Impossible'
	elif len(s) == 1:
		return 'Impossible'
	else:
		c = s[0]
		mid = s[len(s) // 2]
		temp = c * (len(s) // 2) + mid + c * (len(s) // 2)
		if temp == s:
			return 'Impossible'
	n = len(s)
	for i in range(1, n):
		if s[i] == s[i - 1]:
			temp = s[i:] + s[:i]
			if temp != s and isPalindrom(temp, n):
				return 1
	return 2
s = input()
print(solve(s))


import sys
a = input()

def check(x, y):
	return True if x != y and x == x[::-1] else False
n = len(a)
for i in range(1, len(a)):
	if check(a[i:] + a[:i], a):
		print(1)
		sys.exit(0)
for i in range(1, len(a) // 2 + len(a) % 2):
	t = a[-i:] + a[i:-i] + a[:i]
	if check(t, a):
		print('2')
		sys.exit(0)
print('Impossible')


st = input()
le = len(st)
if le == 1:
	print('Impossible')
else:
	flag = False
	for i in range(1, le // 2):
		if st[i] != st[i - 1]:
			flag = True
			break
	if not flag:
		print('Impossible')
	else:
		flag = True
		for i in range(le):
			ne = st[i:] + st[:i]
			if ne == ne[::-1] and ne != st:
				flag = False
				break
		if flag:
			print(2)
		else:
			print(1)


from collections import defaultdict, Counter

def solution(s):
	cnt = Counter(s)
	lncnt = len(cnt)
	if lncnt == 1:
		return 'Impossible'
	elif lncnt == 2:
		for elem in cnt.values():
			if elem == 1:
				return 'Impossible'
	n = len(s)
	for i in range(1, n):
		temp = s[i:] + s[:i]
		if temp == temp[::-1] and temp != s:
			return 1
	return 2

def main():
	stri = input()
	print(solution(stri))
main()


def ispal(t):
	return t == t[::-1]

def main(s):
	if len(set(s)) == 1:
		return 'Impossible'
	for i in range(1, len(s)):
		if s[i:] + s[:i] != s and ispal(s[i:] + s[:i]):
			return 1
	if len(s) % 2 == 1 and len(set(s[:len(s) // 2] + s[len(s) // 2 + 1:])) == 1:
		return 'Impossible'
	return 2
print(main(input()))