Програмчлалын олимпиадын бодлогын архив

Сайн нууцлал гэдэг нь сайн нууц үг сонгохоос эхэлдэг. Туршлагаас үзэхэд нууц үгийг санамсаргүйгээр үүсгэх нь сайн арга юм. Гэвч үүний дутагдалтай тал нь дурын үсэг болон тооноос бүрдсэн нууц үгийг санах нь хэцүү. Үсэг болон тооны оронд хэд хэдэн үгүүдийг санамсаргүйгээр сонгох замаар нууц үг үүсгэж болно. Дараах өгөгдлүүд байгаа бол үүсгэж болох боломжит бүх нууц үгүүдийн тоог ол.
• Үгсийн сан
• Нэг нууц үгэнд байх үгийн тоо
• Нууц үгийн урт

Input

Эхний мөрөнд тестийн тоо t ( 1 ≤ t ≤ 100 ). Үүний дараа тест бүр нь дараах байдалтай байна.
• Үгсийн сан дахь үгийн тоо m(1 ≤ m ≤ 7776), нэг нууц үгэнд байх үгийн тоо n(1 ≤ n ≤ 5), асуулгын тоо q(1 ≤ q ≤ 20).
• Үгсийн сан: m мөрөөс тогтох бөгөөд мөр бүр нэг үг агуулна. Үгнүүд нь жижиг үгээс тогтох ба урт нь 2 –оос их, 11-ээс бага байна. Ямар ч үг бусад үгнүүдийнхээ альных нь ч дэд мөр болохгүй.
• Эерэг тоо L_i (1 ≤ L_i ≤ 50) агуулах q ширхэг мөр байх ба L нь асуулгын утга юм.

Output

Тест бүрийн хувьд
• q ширхэг мөр байх ба мөр бүр нь үгсийн санг ашиглан тухайн асуулгын утгад харгалзах урттай нууц үг хэдийг үүсгэх боломжын тоо байна.

Example

Input:
1
4 2 2
net
spoj
test
prob
7
8


Output:
6
9