Một xâu được gọi là xâu đối xứng nếu nó đọc giống nhau từ trái sang phải và từ phải sang trái. Ví dụ: abcba, abba, xyzzyx... là xâu đối xứng, abc, abab, mnnn không phải là xâu đối xứng.

Bạn được cho một xâu \(S\) bao gồm các chữ cái tiếng Anh viết thường. Mỗi lần biến đổi, bạn có thể chọn bất kỳ một vị trí nào trong xâu rồi thay đổi chữ cái ở vị trí đó thành bất kỳ chữ cái tiếng Anh viết thường nào khác và độ dài của xâu là không đổi. Bạn cũng có thể hoán vị thứ tự của các chữ cái trong xâu một cách tùy ý. Chú ý rằng hoán vị không được tính là một phép biến đổi.

Yêu cầu: Hãy tính số lần biến đổi tối thiểu để xâu \(S\) trở thành một xâu đối xứng. Nếu sau số lần biến đổi tối thiểu ấy có nhiều xâu \(S\) thỏa mãn, in ra xâu có thứ tự từ điển nhỏ nhất.

Input

• Nhập từ bàn phím xâu \(S\) bao gồm các chữ cái tiếng Anh viết thường.

Output

• In ra xâu đối xứng có thứ tự từ điển nhỏ nhất có thể nhận được sau số lần biến đổi tối thiểu.

Scoring

• Nếu chương trình chạy đúng những trường hợp \(N \leq 10\) và chỉ có \(3\) loại ký tự a, b và c, thí sinh sẽ được \(40\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 1000\), thí sinh sẽ được \(80\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^5\), thí sinh sẽ được \(100\) điểm.

Example

abac

abba

abacad

aabbaa