Sasha và cái tên khác

Cho một xâu $s$ là xâu đối xứng (palindrome) — đọc xuôi và đọc ngược cho ra cùng một xâu. Bạn được phép cắt $s$ thành đúng $k+1$ đoạn liên tiếp (không lật ngược đoạn nào), rồi ghép các đoạn này theo một thứ tự bất kỳ để tạo thành một xâu mới $s^{\prime }$.

Hãy tìm giá trị nhỏ nhất của $k$ sao cho có thể chọn cách cắt và cách ghép phù hợp để $s^{\prime }$ vừa là một xâu đối xứng, vừa khác với xâu ban đầu $s$. Nếu không tồn tại $k$ thoả mãn, in ra Impossible.

Dữ liệu vào

• Một dòng duy nhất chứa xâu $s$ ($1\le |s|\le 5000$), chỉ gồm các chữ cái Latin in thường.
• Đảm bảo $s$ là xâu đối xứng.

Dữ liệu ra

• In ra một số nguyên là giá trị nhỏ nhất của $k$, hoặc Impossible nếu không tồn tại.

Ràng buộc

• $1\le |s|\le 5000$.
• $s$ chỉ gồm chữ cái Latin in thường và là xâu đối xứng.

Ví dụ