Problem C: Coverity Crossword

crossword

What is your crossword telling you today? Can you scan your code for patterns, in the time it takes to get a cup of coffee? You have just landed a job at Coverity, and your first challenge is to demonstrate your searching and testing abilities. Can you find and analyze code that looks like random strings? Up to ten secret messages are hidden in a crossword of size 8x8, and your task is to determine if they are all present in the code or not.

Secrets are hidden horizontally, from left to right, vertically, from top to bottom, and diagonally, from top-left to bottom-right.

Input Format

The first line of the input contains an integer T (1 ≤ T ≤ 100), the number of test cases. Then follow T test cases. Each case starts with an integer N on a line (1 ≤ N ≤ 10), the number of words we are searching for. Each of the next N lines contains a non-empty string of length at most 8 characters over the alphabet [A-Z], the words we are searching for. Then follows 8 lines, each containing a string of exactly 8 characters over the alphabet [A-Z], the i'th horizontal line in the crossword, from left to right, starting from the topmost line down to the bottommost line.

Output Format

For each test case print on a separate line either "Yes" or "No", the answer to the question "Is it the case that all N messages are present in the crossword?"

Sample Input

2
8
BLAST
COVERITY
CPSC
PRIZES
PROBLEMS
PSC
SOLVING
TESTING
SPRIZESS
SROSNPSP
COVERITY
ABLASTIG
NLSVINGC
TESTINGP
EMSPONYS
PSYNPSGC
2
COOL
LOL
OCCOOOCL
OCCLCLOO
OLOOCLOL
LLOOCOOC
LOCCCOLL
COCCOLLO
OLOLOCOL
LLOOCCOO

Sample Output

Yes
No

Peter Høyer
CCPC 2014