Almost everyone is familiar with crossword puzzles. Here you have to deal with a special kind of crossword puzzle that is adequate for an automated solver. A description of the puzzle and a list of admissible words (the dictionary) is given, and the goal is to find the number of possible solutions, if any exists, for the puzzle using the given dictionary. The puzzle is represented as a grid of white and black squares. A solution is a subset of dictionary words that fill all the sequences of horizontal or vertical white squares in such a way that all the horizontal and vertical crossings formed are still valid dictionary words. One-letter sequences do not need to be in the dictionary. An example of a crossword puzzle in which white and black squares are respectively represented by the ‘.’ and ‘#’ characters, a word dictionary and a solution for the puzzle is as follows: .......... .....#.... .#......#. ....#..#.. ..##...#.. ..#.....## ...#...#.. ..#..##... ..#....... ..#....#.. aaacalalaoaliap atencao atlanta camilo doar dr duo eam eis el epoca et icar ileso is la loto mal men merito mi no oaristo oo os pios resto roa roca rt sa senil si tule variedades verdadeiro variedades epoca#tule r#camilo#n doar#la#si aa##men#al dr#resto## eis#roa#ap is#mi##ali rt#atencao oo#loto#os Your task is to develop a program to solve the described crossword puzzles. Input The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The input consists of a 10 × 10 puzzle configuration and a word dictionary. For the puzzle each input line is a sequence of ‘.’ and ‘#’ characters. You may assume that the given configuration is always correct. The dictionary words start immediately after the last line of the puzzle. Each word is a sequence of lower case letters, without accents and separated by spaces. The dictionary terminates when the end-of-file is reached from the standard input. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The program should output the number of solutions that the given crossword puzzle accepts. Sample Input 1
2/2 .......... .....#.... .#......#. ....#..#.. ..##...#.. ..#.....## ...#...#.. ..#..##... ..#....... ..#....#.. aa ac al alao ali ap atencao atlanta camilo doar dr duo eam eis el epoca et icar ileso is la loto mal men merito mi no oaristo oo os pios resto roa roca rt sa senil si tule variedades verdadeiro Sample Output 1