Bonus Word

Lingo was once a popular game show where contestants guess words. In the original version a contestant guesses a five-letter word each round.

Between the regular guessing rounds, a contestant wins a bonus prize by guessing a ten-letter word. The ten-letter word is shown with its letters permuted, and a few of the letters are colored. A colored letter is already in the right position. Ten-letter words are not that common, so the word is often a compound: two shorter words written one after the other. In this problem the ten-letter word always has that form.

Given a dictionary and a sequence of ten letters, compute every possible solution to the ten-letter word game. Two solutions count as different when they are built from different parts, even if the concatenation is the same.

The first line has an integer $t$ ($1 \le t \le 100$), the number of test cases. Each test case is given as follows.

• One line with an integer $n$ ($1 \le n \le 200$), the number of words in the dictionary.
• $n$ lines, each with one dictionary word. Each word is 1 to 9 characters long and consists of lowercase letters only.
• One line with an integer $q$ ($1 \le q \le 100$), the number of queries.
• $q$ lines, each with one query string. Each query is exactly 10 characters long and consists of uppercase and lowercase letters. A lowercase letter is in the right position, and an uppercase letter may be in the wrong position.

All dictionary words inside a single test case are distinct.

For each query, print the following.

• One line with an integer $s$, the number of solutions.
• $\min(1000, s)$ lines, each holding one solution written as two dictionary words joined by a hyphen (-).

Order the solutions of one query lexicographically. If there are more than 1000 solutions, print only the first 1000.

Let $x$ and $y$ be strings of equal length and let $x_i$ be the $i$-th character of $x$. Then $x$ precedes $y$ lexicographically when there is an $i$ with $x_i < y_i$ and $x_j = y_j$ for every $j < i$. In this problem the hyphen precedes every letter.