本問題請你轉換一字串使之變成迴文字串 (一種從前面寫與從後面寫都一樣的字串，例如 abcba)，藉由新增、刪除、取代字母等步驟來轉換成迴文字串，並使轉換的步驟最小化。更精確地說，你可以執行的步驟有三種：
- 新增：插入一字母到字串中任一位置。
- 刪除：刪除字串中任一字母。
- 取代：以一個字母取代字串中任一字母。
每執行上述三種步驟中的任一種即算一次，你必需使轉換步驟愈少愈好。
例如字串 abccda，如果只允許以新增字母的方式轉換字串，則最少需要兩個步驟，若允許以取代的方式轉換字串，則最少僅需一個步驟。當然，本問題是允許你三種步驟都能使用。
Input
輸入的第一列有一個整數 $T$ ($1\leq{T}\leq{10}$) 表示接下來有 $T$ 列測試資料，每列測試資料皆為一個僅含小寫字母的字串，字串長度不會超過 1000 個字元。
Output
請對每組測試資料輸出其編號，與使字串變成迴文字串的最少步驟為何。
Sample Input
6
tanbirahmed
shahriarmanzoor
monirulhasan
syedmonowarhossain
sadrulhabibchowdhury
mohammadsajjadhossain
Output for Sample Input
Case 1: 5
Case 2: 7
Case 3: 6
Case 4: 8
Case 5: 8
Case 6: 8