Xâu đối xứng (Palindrome) là một xâu khi đọc từ trái sang phải hoặc đọc từ phải sang trái đều như nhau.

Ví dụ: ABBA là một xâu đối xứng, ITUTI cũng là xâu đối xứng nhưng ITUTC lại ko phải. Một xâu không đối xứng ta có thể chuyển thành một xâu đối xứng bằng cách thay đổi một số kí tự của nó.

• Gọi một xâu là K-palindrome nếu nó có thể chuyển thành xâu đối xứng bằng việc thay đổi nhiều nhất K kí tự.

Ví dụ: ABBA là 1 xâu 0-palindrome.

Chỉ còn ít phút nữa là trận tứ kết Vietnam - Korea bắt đầu và các bạn sinh viên UTC đang rất nôn nóng bởi vẫn phải ngồi học lập trình nâng cao, thấy vậy, Thầy TichPX liền đố các bạn một số câu hỏi, nếu các bạn trả lời được trong 1s thì thầy sẽ cho nghỉ tiết học để các bạn có thể thoải mái xem bóng đá.

Câu hỏi như sau: Cho một xâu S độ dài N bao gồm các kí tự in thường từ 'a' -> 'z' và một số nguyên K. Hãy viết chương trình tìm "độ dài xâu con dài nhất" của S mà xâu con đó là một xâu k-palidrome. Các bạn hãy viết chương trình giải bài toán trên của Thầy nhé.

Input

Dòng đầu tiên là số T là số lượng testcase. Các dòng tiếp theo mô tả các test case.

Mỗi testcase bao gồm 1 xâu S \(( 1 <= N <= 1000)\) ( N là độ dài của S ) và số nguyên K. \((0 <= K <= N).\)  

Output

Với mỗi testcase, in ra một dòng duy nhất: độ dài xâu con dài nhất của S và xâu con đó là một k-palidrome.

Ví dụ

Input

3
abba 0
mate 1
zabcddcbxy 1

Output

4
3
8