Dọc theo con đường tơ lụa những con lạc đà cần mẫn chuyên chở tơ lụa, hương liệu và ngọc ngà đá quý của phương đông. Đá quý được phân thành 26 loại ký hiệu bằng chữ cái la tinh thường từ a đến z. Các lái buôn muốn bán được hàng với giá càng cao càng tốt. Trong chuyến đi này một lái buôn mang theo bộ đá quý gồm n viên. Ông xâu tất cả thành chuỗi và bày ra trên thảm trước một lãnh chúa hùng mạnh. Vị lãnh chúa cân nhắc đánh giá chất lượng bộ đá quý để quyết định có nên mua hay không. Theo quy tắc truyền thống của địa phương, giá trị của chuỗi ngọc phụ thuộc vào sự xuất hiện các cặp ngọc (~a_i~, ~b_i~), tức là phải có ngọc loại ~a_i~ đứng trước loại ~b_i~ ~(i = 1 ... k)~. Nếu giá trị chuỗi ngọc đủ lớn, lãnh chúa sẽ mua toàn bộ chuỗi ngọc.

Yêu cầu: Cho biết n và xâu S thể hiện các loại ngọc trong chuỗi, cách định giá trị chuỗi ngọc của địa phương. Hãy xác định giá trị của chuỗi ngọc.

Dữ liệu:

• Dòng thứ nhất chứa số nguyên dương T, là số lượng test có trong file dữ liệu
• Mỗi test có cấu trúc như sau:
  • Dòng thứ nhất chứa hai số nguyên dương n, k.
  • Dòng thứ 2 chứa xâu S.
  • Mỗi dòng trong k dòng sau chứa xâu 2 ký tự xác định cặp có giá trị.

Kết quả: Ghi ra một số nguyên – giá trị chuỗi ngọc

Ví dụ:

Input

1
7 3
abacaba
ab
ac
bb

Output

7

* Giới hạn:* 0 < T ≤ 10; 0 < n ≤ ~10^5~; 1 ≤ k ≤ ~10^5~.

* Ràng buộc:*

• Subtask1: 50% số test ứng với 50% số điểm của bài có n ≤ ~10^3~; k ≤ ~10^3~.
• Subtask2: 20% số test khác ứng với 20% số điểm của bài có n ≤ ~10^3~; k ≤ ~10^5~
• Subtask3: 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì.