Ở vương quốc KMA tươi đẹp, trong khi người người, nhà nhà đều đang tập trung cày code để chuẩn bị cho kì thi Hackathon sắp tới thì Sơn – một trong rất nhiều con dân xấu số nơi đây, đang phải đối đầu với kì thi mang tính sống còn: thi lại thể chất I.

Có lẽ ai cũng biết, bài thi kết thúc học phần thể chất I có nội dung là chạy nước rút. Tuy nhiên, đối với những người thi lại, đề thi đã không còn đơn giản như vậy nữa!

Ở điểm xuất phát, cô Hoa đặt một chiếc đèn tín hiệu gồm 3 màu xanh, đỏ, vàng (x,d,v). Thí sinh sẽ chỉ được phép xuất phát khi đèn tín hiệu chuyển sang màu xanh!

Cụ thể:

Chiếc đèn sẽ lặp lại tín hiệu sau mỗi N giây và tại giây thứ i-th, đèn sẽ chuyển sang màu s_i.

Màu của đèn tín hiệu được biểu diễn bởi một chuỗi kí tự.

Ví dụ: nếu chuỗi tín hiệu là s= "dxxdv", khi đó đèn tín hiệu sẽ hoạt động theo nguyên tắc: “đỏ-xanh-xanh-đỏ-vàng- đỏ-xanh-xanh-đỏ-vàng- đỏ-xanh-xanh-đỏ-vàng...”  và tiếp tục lặp lại như vậy.

Sau khi nắm bắt được quy luật đổi màu của đèn tín hiệu giành Sơn cần phải tính khoảng thời gian tối thiểu mà mình phải đợi để xuất phát trong trường hợp tín hiệu đèn bắt đầu là xấu nhất!

Với chuỗi nhập vào là là s= "dxxdv" và đèn tín hiệu hiện tại là màu đỏ(d), sẽ có 2 trường hợp xảy ra là đèn sẽ chuyển xanh sau 1s hoặc sau 3s. Đáp án là 3s – khoảng thời gian tối thiểu có thể xuất phát trong trường hợp xấu nhất.

Input

Dòng đầu tiên là số lượng test case t ( 1 ≤ t ≤ 10⁴ ).

Dòng đầu tiên của mỗi test case là một số nguyên n và một kí tự c (1≤n≤2.10⁵, c là một trong những màu đèn tín hiệu hợp lệ d, v hoặc x) tương ứng là độ dài của chuỗi tín hiệu s và tín hiệu đèn hiện tại.

Dòng thứ 2 là một chuỗi tín hiệu s có độ dài n, chỉ bao gồm các kí tự d,v,x.

Test case sẽ luôn được đảm bảo rằng:

Luôn tồn tại kí tự ‘x’ và tín hiệu hiện tại c trong chuỗi s.

Subtask1:   có 25% số lượng testcase t  ≤ 10² và độ dài n của chuỗi tín hiệu s ≤ 10⁵.

Subtask2:   75% lượng testcase còn lại dữ liệu như đề bài.

Output

Gồm t dòng, mỗi dòng gồm 1 số nguyên là khoảng thời gian tối thiểu phải đợi.

Example

Input:
6
1 x
x
3 d
ddx
5 v
vddxv
7 d
vxdxvdx
5 d
vxxdv
9 v
dddxvvvxv

Output:
0
2
4
1
3
4