ACRYM - Acronym

no tags 

An acronym is made of up the initial letter(s) of the words in a phrase, such as EU (European Union) and BREXIT (BRitish EXIT). In this problem, we can also either ignore or consider the conjunction "and", and the following adpositions "in", "on", "at", "to", "of", "from", "for" and "with" when making the acronym, such as BENELUX (BElgium, NEtherlands and LUXembourg) and RADAR (RAdio Detection And Ranging).

Given an acronym A, and a list of N strings W1, W2 ... WN, you would like to find out the number of possible combinations of making the given acronym by using all the N strings following their order. That is, the acronym must be made up of at least one initial letter of each word, except the above-mentioned conjunction and adpositions (either skip or use it). Both A and the N strings only consist of lowercase latin letters.

Input

The first line is the number of test cases T. (1 ≤ T ≤ 20)

For each test case, it starts with one integer N. (1 ≤ N ≤ 200)

Next line is a string A. (1 ≤ |A| ≤ 104)

Following N lines, each consisting of one string Wi. (1 ≤ |Wi| ≤ 50)

It is guaranteed that W1 is neither conjunction nor adposition.

Output

Output one integer indicating the number of possible combinations.

Example

Input:
3
3
duckhim
duck
hello
moto

7
natiofforessaa
national
office
for
forest
safety
in
aachen

4
whiskey
what
is
secret
key

Output:
0
4
1

Explanation

In case 1, no combination is possible.

In case 2, there are four possible combinations:

  • NATIonal OFfice for FORESt SAfety in Aachen
  • NATIonal OFfice for FORESt Safety in AAchen
  • NATIonal Office For FORESt SAfety in Aachen
  • NATIonal Office For FORESt Safety in AAchen

In case 3, only one possible combination exists:

  • WHat Is Secret KEY

hide comments
suhash: 2020-06-07 14:50:32

Since there is no update from the author, I created a new problem with better test data: https://www.spoj.com/problems/ACRYM2/

It would make sense to lower the constraints on this problem as there is now a harder version.

RE: It seems unfair to modify the test data on this problem because I cannot rejudge the submitted solutions, but it makes sense to lower the time limit. I have lowered it from 0.8s to 0.4s.

Thanks! I'll update the constraints on the harder version to be higher in that case.

Last edit: 2020-06-07 20:30:52
suhash: 2020-05-26 14:30:54

Nice problem, but the test cases are weak. Currently, the answer fits in a signed 32 bit integer. Issues with the current version:

1.) The answer has over 200 digits for this case (for e.g.): |A| = 1000, N = 200, |Wi| = 50
A = aaaaa.......1000 times
Wi = aaaaa......50 times (1 <= i <= 200).
It might be better to modify the problem to instead print the answer modulo a small value (say 10^9+7).

2.) See my last 2 submissions:
[ID: 26044685] has complexity - O(T * |A| * N * |Wi|) and runs in 0.46 sec.
[ID: 26044659] has complexity - O(T * |A| * (N + |Wi|)) and runs in 0.58 sec.

The sub-optimal solution runs faster, which means the current test cases are weak. The above mentioned test case (with |A| = 10000) will also ensure that a sub-optimal solution gets TLE. :)

Last edit: 2020-05-26 17:30:09

Added by:him0727
Date:2020-05-14
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem