Gotta Print 'Em All

Gray has received $N$ documents this morning and he wants to print as many of them as he can within his budget. He hasn't actually set the printing budget yet, but he wonders how many of the $N$ documents he can print at most if he has a certain budget.

Printing each document requires a piece of paper that costs $P$ units of money, and some amount of ink. Each of the $N$ documents has a size of $X \times Y$, and each of the $X\times Y$ blocks of a document can be empty or can contain an alphanumeric character. If a block is empty, it will be denoted with a dot ('.'). Printing each character requires 1 drop of ink. Each drop of ink costs $K$ units of money. So, the cost of printing a document will be the total cost of ink for the document and the cost of 1 piece of paper.

For example, the following is a document with a size of $4 \times 3$:

1c.
...
.0.``````

To print this document, 5 drops of ink and 1 piece of paper will be required.

As we already know the structure of each of the N documents, Gray now has $Q$ queries to be answered. In each query, he will give a suggested budget and you will have to answer the query by telling him the maximum number of documents he can print within the budget.

Input

The first line contains an integer $T$ ($1 ≤ T ≤ 10$) - denoting the number of test cases. For each test case:

The first line contains 3 space-separated integers $N$, $X$, $Y$ ($1 ≤ N ≤ 10^5$; $1 ≤ X, Y ≤ 10$), the number of documents and the dimensions of each documents.

The next line contains 2 space-separated integers $P$, $K$ ($1 ≤ K, P ≤ 10^9$) - denoting the cost of a sheet of paper and cost of a drop of ink, respectively.

Then $N \times X$ lines follow, each having $Y$ characters - which define the $N$ documents. Each character can be an alphabet ('A'-'Z', 'a'-'z') or a digit ('0'-'9') or a dot ('.') The first $X$ of these lines define the 1st document, the next $X$ lines define the 2nd document, and so on.

The next line contains a single integer $Q$ ($1 ≤ Q ≤ 10^5$) - denoting number of queries.

Each of the next $Q$ lines contain an integer $B$ ($1 ≤ B ≤ 10^{14}$) - budget for each query.

Output

For each test case, print $Q$ lines of output, one for each query.

For each query, print a single integer - the maximum number of documents Gray can print so that the cost doesn't exceed the budget for that query.

Sample

Input	Output
2 3 4 3 1 1 z.A 1c. ... .o. ABC 123 abc 777 ... ... ... ... 5 1 6 20 15 10 1 1 1 1 1 z 1 1	1 1 3 2 2 0
In the first test case of the sample, printing 1st document will cost 6 units (5 for ink and 1 for piece of paper). Similarly, 2nd document costs 13 units and 3rd one costs 1 units. In 4th query, the budget is 15. With this budget he can either print document 1 and 3 or document 2 and 3. So maximum number of documents printable in this query will be 2.