보너스 단어

링고는 한때 인기가 많았던 단어 맞히기 게임 쇼다. 원래 방식에서는 참가자가 매 라운드마다 다섯 글자 단어를 맞힌다.

일반 라운드 사이에는 열 글자 단어를 맞히면 보너스 상품을 받는 순서가 있다. 열 글자 단어는 글자 순서를 뒤섞어서 보여 주고, 그중 몇 글자에는 색이 칠해져 있다. 색이 칠해진 글자는 이미 제자리에 놓여 있다는 뜻이다. 열 글자짜리 단어는 그리 많지 않아서, 짧은 단어 두 개를 이어 붙인 합성어가 자주 나온다. 이 문제에서 열 글자 단어는 항상 이 형태라고 가정한다.

사전과 열 글자짜리 문자열이 주어지면, 열 글자 단어 게임의 답이 될 수 있는 경우를 모두 구하시오. 이어 붙인 결과가 같더라도 재료가 된 두 단어가 다르면 서로 다른 답으로 센다.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 100$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 첫 줄에 사전에 실린 단어의 개수 $n$ ($1 \le n \le 200$).
• 다음 $n$개 줄에 사전 단어가 한 줄에 하나씩. 각 단어의 길이는 1 이상 9 이하이고, 알파벳 소문자로만 이루어져 있다.
• 다음 줄에 질의의 개수 $q$ ($1 \le q \le 100$).
• 다음 $q$개 줄에 질의 문자열이 한 줄에 하나씩. 각 질의의 길이는 정확히 10이고, 알파벳 대문자와 소문자로 이루어져 있다. 소문자는 제자리에 있는 글자이고, 대문자는 제자리가 아닐 수도 있는 글자다.

한 테스트 케이스 안의 사전 단어는 모두 서로 다르다.

각 질의마다 다음을 출력한다.

• 한 줄에 답의 개수 $s$.
• 이어서 $\min(1000, s)$개 줄에 답을 하나씩. 답은 사전 단어 두 개를 붙임표(-)로 이어 쓴다.

한 질의의 답은 사전순으로 정렬해 출력한다. 답이 1000개보다 많으면 앞의 1000개만 출력한다.

길이가 같은 두 문자열 $x$, $y$가 있고 $x_i$가 $x$의 $i$번째 글자라고 하자. 어떤 $i$에서 $x_i < y_i$이고 $j < i$인 모든 $j$에서 $x_j = y_j$이면, $x$가 $y$보다 사전순으로 앞선다. 이 문제에서 붙임표는 모든 알파벳보다 앞선다.