Cho xâu ~st~ và ký tự ~c~. Viết chương trình tìm chiều dài xâu con dài nhất của ~st~ có chứa ký tự ~c~ thỏa mãn xâu Palindrome.

Input

Dòng đầu tiên chứa số nguyên ~T~ là số testcase thỏa ~1 \le T \le 10~. Mỗi testcase tiếp theo gồm:

• dòng đầu chứa ký tự ~c~ thuộc Alphabet in thường.

• dòng tiếp chứa xâu ~st~ thỏa chiều dài nhỏ hơn hoặc bằng 1000 ký tự thuộc Alphabet in thường.

Output

In ra kết quả cần tìm.

Samples

Sample Input 1

2
a
dcbabcd
b
bbbb

Sample Output 1

7
4