读书是 Sasha 的爱好之一。有一次,他在读一本书时,认识了一个不寻常的人物。这个角色这样讲述自己:“在许多国家,我的名字有很多。精灵中的米斯兰迪尔,矮人中的塔昆,奥洛林。我年轻时在被遗忘的西方,在南印卡努斯,在北甘道夫;我没有去东方。”
在那一刻,萨沙想,这个角色在东方该怎么称呼?在东方,所有名字都是回文。如果一个字符串向后读与向前读相同,则该字符串是回文。例如,“kazak”、“oo”和“r”等字符串是回文,但字符串“abb”和“ij”则不是回文。
萨沙相信英雄将以东方诸神之一的名字命名。只要不能有两个相同的名字,那么在东方,人们就会这样做:他们把原来的名字作为字符串写在一张纸上,然后将纸剪裁最少$$$k$$$次,这样就得到了$$$k+1$$$张纸,其中包含初始字符串的子字符串,然后将这些碎片组合在一起得到新的字符串。棋子不能翻转,只能洗牌。
通过这种方式,可以使用 $$$3$$$ 剪切从字符串 f|de|abc|g 中获得字符串 abcdefg(通过用子字符串 f 和 abc 交换文件)。使用相同的剪切无法接收字符串 cbadefg。
更正式地说,Sasha 希望对于给定的回文 $$$s$$$ 找到这样的最小值 $$$k$$$,您可以将此字符串切割成 $$$k + 1$$$ 部分,然后以最终字符串将是回文的方式将它们联合起来,并且它不会等于初始字符串 $$$s$$$。如果没有答案,则打印“Impossible”(不带引号)。
输入
第一行包含一个字符串 $$$s$$$ ($$$1 \le |s| \le 5\,000$$$) - 初始名称,仅由小写拉丁字母组成。保证 $$$s$$$ 是回文。
输出
打印一个整数 $$$k$$$ — 获得新名称所需的最少切割次数,或“不可能”(不带引号)。
示例
输入 #1
nolon
输出 #1
2
输入 #2
otto
输出 #2
1
输入 #3
qqqq
输出 #3
Impossible
输入#4
kinnikkinnik
输出#4
1
注意
在第一个示例中,您可以在以下位置剪切字符串:no|l|on,然后按如下方式将它们联合起来 on|l|no。可以证明,不存在一刀切的解。
在第二个示例中,您可以在中间切断字符串,并交换和平,这样您就会发出嘟嘟声。
在第三个示例中,您无法创建一个字符串,它不会等于第一个字符串。
在第四个示例中,您可以删除后缀 nik 并将其添加到开头,这样您就得到 nikkinnikkin。