Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Rdeaalbe
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1926Accepted: 479

Description

Background
As you probably know, the human information processor is a wonderful text recognizer that can handle even sentences that are garbled like the following:
The ACM Itrenntaoial Clloegaite Porgarmmnig Cnotset (IPCC)
porvdies clolgee stuetnds wtih ooppriuntetiis to itnrecat
wtih sutednts form ohetr uinevsrtieis.

Problem
People have claimed that understanding these sentences works in general when using the following rule: The first and last letters of each word remain unmodified and all the characters in the middle can be reordered freely.
Since you are a skeptical ACM programmer, you immediately set on to write the following program:
Given a sentence and a dictionary of words, how many different sentences can you find that could potentially be mapped to the same encoding?

Input

The first line contains the number of scenarios. Each scenario begins with a line containing the number n of words in the dictionary (0 <= n <= 10000), which are printed on the following n lines. After this there is a line containing the numbermof sentences that should be tested with the preceding dictionary (0 <= m <= 10000) and then m lines containing those sentences. The sentences consist of letters from a..z, A..Z and spaces only and have a maximal length of 10000 characters. For each word in the dictionary a limitation of 100 characters can be assumed.

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. For each sentence output the number of sentences that can be formed on an individual line. It is guaranteed that this number can be expressed using a signed 32-bit datatype. Terminate the output for the scenario with a blank line.

Sample Input

2
3
ababa
aabba
abcaa
2
ababa
abbaa
14
bakers
brakes
breaks
binary
brainy
baggers
beggars
and
in
the
blowed
bowled
barn
bran
1
brainy bakers and beggars bowled in the barn

Sample Output

Scenario #1:
2
2

Scenario #2:
48

Source

TUD Programming Contest 2005, Darmstadt, Germany

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator