Pattern Recognition

Given an image consisting only lowercase letters, for each query you should count the number of patterns in the image.

Formally, an image is a matrix with $n$ rows and $m$ columns, and each cell of the matrix contains a character. Considering a string consisting of lowercase letters, we can place it horizontally or vertically, so it has following shapes:

We can bend it $90$ degrees, and we get some new shapes:

In a word, a pattern is a string with these $6$ possible shapes:

For example, pattern abcd can have following shapes:

Kanari loves CV(Computer Vision), he writes a CNN(Convolutional Neural Network) to count the number of patterns in an image. Kanari is so cute, and the accuracy tends to $100\%$ after a long time parameter adjustment. Can you solve it too?

This problem contains multiple test cases.

The first line of the input contains an integer $T (1 \leq T \leq 5)$ indicating the number of test cases.

For each test case, the first line contains three integers $n, m, q (n \geq 1, m \geq 1, 1 \leq n \times m \leq 10^5)$, representing the width of the image, the height of the image and the number of queries.

Each of the next $n$ lines contains $m$ characters representing the image.

Each of the next $q$ lines contains a string representing a query.

It is guaranteed that the sum of length of all queries in a test case is no more than $10^5$.

For each query, output the number of corresponding patterns occurred in the image. Note that two occurences are different if and only if the SET of positions for the pattern in the image are different.

2
10 10 1
xxxxxxxxxx
xbcdxxxxxx
xaxxxdcbax
xxxdxxxxxx
xxxcbaxxxx
xxxxxxabxx
xaxaxxdcxx
xbxbxxxxdc
xcxcxxxxxb
xdxdxxxxxa
abcd
5 5 2
xsssx
xxbxx
xbabx
xxbxx
xxxxx
ab
sss

6
4
1

Explanation for the second testcase:

For pattern ab , the occurences are { (2, 3), (3, 3) }, { (3, 2), (3, 3) }, { (3, 3), (3, 4) }, { (3, 3), (4, 3) }.
For pattern sss , the only occurence is { (1, 2), (1, 3), (1, 4) }.

2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛