Trên một khoảng sân rộng có chiều dài \(L\), người ta đặt một số thùng hàng. Dưới đây là một hình ảnh về sân có chiều dài \(10\), có chứa \(5\) thùng hàng \(A, B, C, D, E\).

Hoàng muốn di chuyển các thùng hàng để tạo ra một khoảng sân có độ rộng tối thiểu là \(W\) để có thể chơi bóng cùng các bạn của mình. Mỗi bước, Hoàng có thể di chuyển một thùng hàng sang trái hoặc sang phải nếu vị trí vẫn nằm trong sân và vị trí đó còn trống.

Với ví dụ trên, khi Hoàng cần một khoảng sân độ rộng tối thiểu là \(3\), thì dưới đây là một cách di chuyển các thùng hàng. Cách di chuyển này cần \(2\) bước di chuyển.

Nếu Hoàng cần một khoảng sân độ rộng tối thiểu là \(4\), thì dưới đây là một cách di chuyển các thùng hàng. Cách di chuyển này cần \(4\) bước di chuyển.

Nếu Hoàng cần một khoảng sân độ rộng tối thiểu là , thì dưới đây là một cách di chuyển các thùng hàng. Cách di chuyển này cần bước di chuyển.

Yêu cầu: Cho vị trí ban đầu của các thùng hàng và giá trị \(W\), bạn hãy giúp Hoàng tính số bước di chuyển ít nhất.

Input

• Dòng đầu tiên ghi số \(T\) là số bộ dữ liệu \((T \leq 10)\)
• \(T\) dòng tiếp theo, mỗi dòng mô tả một bộ dữ liệu. Mỗi dòng chứa một xâu kí tự \(s\) mô tả sân có độ dài không quá \(5 \times 10^5\) và số nguyên dương \(W\) cách nhau bởi dấu cách. Xâu kí tự \(s\) chỉ gồm dấu chấm hoặc kí tự X, trong đó kí tự chấm thể hiên vị trí sân không có thùng hàng và kí tự X thể hiện vị trí sân có thùng hàng.

Output

• In ra \(T\) dòng, mỗi dòng chứa một số nguyên là ra số lần di chuyển các thùng hàng ít nhất.

Scoring

• Subtask #1 (\(10\%\) số điểm): Độ dài xâu \(s\) không vượt quá \(50\) và có không quá \(3\) thùng hàng
• Subtask #2 (\(10\%\) số điểm): Độ dài xâu \(s\) không vượt quá \(20\)
• Subtask #3 (\(10\%\) số điểm): Độ dài xâu \(s\) không vượt quá \(50\)
• Subtask #4 (\(10\%\) số điểm): Độ dài xâu \(s\) không vượt quá \(200\)
• Subtask #5 (\(25\%\) số điểm): Độ dài xâu \(s\) không vượt quá \(5000\)
• Subtask #6 (\(20\%\) số điểm): Độ dài xâu \(s\) không vượt quá \(50000\)
• Subtask #7 (\(15\%\) số điểm): Không có ràng buộc gì thêm

Example

4 
.XX..XX.X. 2
.XX..XX.X. 3
.XX..XX.X. 4
.XX..XX.X. 5

0
2
4
7