// Solution to "ACronym Maker" by Bob Roos
//
// Input abbreviation, abbrev, and phrase, ignoring insignificant words.
// Search for substrings of abbrev in each of the words phrase[0],
// ..., phrase[numWords-1], then combine results to get number of ways
// to form the abbreviation.

import java.io.*;
import java.util.*;

public class ACM {

 // input-related stuff:
 public static BufferedReader in;
 public static StringTokenizer tok;

 public static String insig[]; // array of insignificant words
 public static String phrase[]; // array of significant words
 public static int numWords; // number of significant words
 public static String abbrev; // the abbreviation
 public static Hashtable lookup; // used to memoize search for substrings

 // "main" contains basic input/process/output loop:
 public static void main(String[] args) throws IOException {
   in = new BufferedReader(new InputStreamReader(System.in));

   // Now process the various test cases:
   String line;
   while (!(line = in.readLine().trim()).equals("0")) {
     // Read in the insignificant words:
     int n = Integer.parseInt(line);

     insig = new String[n];
     tok = new StringTokenizer("");
     for (int i = 0; i < n; i++) {
       insig[i] = nextWord();
     }
     while (!(line = in.readLine().trim()).equals("LAST CASE")) {
       tok = new StringTokenizer(line);

      // First item on each line is the abbreviation:
       abbrev = tok.nextToken();

      // Next k items are the words of the phrase:
       numWords = 0;
       int k = tok.countTokens();
       phrase = new String[k];

      // Read in phrase, but only save the significant words:
       for (int i = 0; i < k; i++) {
         String word = tok.nextToken();
         boolean ins = false;

         // Linear search for insignificant words:
         for (int j = 0; j < n; j++)
           if (insig[j].equals(word)) {
             ins = true;
             break;
           }

         // Save the word if it is significant:
         if (!ins)
           phrase[numWords++] = word;
       }

       process(); // Solve this test case
     }
   }
 }


 // Process a single test case:
 public static void process() {

// DEBUG:
//  System.out.print(abbrev = " ");
//  for (int i = 0; i < numWords; i++)
//    System.out.print(phrase[i] + " ");
//  System.out.println();
//

   int k = abbrev.length();
   abbrev = abbrev.toLowerCase();

   // Easy base case -- too many words:
   if (numWords > k) {
     System.out.println(abbrev.toUpperCase() + " is not a valid abbreviation");
     return;
   }

   // "lookup" stores pairs (u,v) of strings and the number of ways that
   // u is a substring of v:
   lookup = new Hashtable();

   int numAbbr = 0; // number of ways to abbreviate

   // Another base case -- exactly one letter in the abbreviation:
   if (k == 1) {

     // There must be at least one word in the phrase, and previous
     // tests guarantee exactly one:
     numAbbr = occurs(abbrev,0,k-1,phrase[0],0,phrase[0].length()-1);
     if (numAbbr == 0)
       System.out.println(abbrev.toUpperCase() + " is not a valid abbreviation");
     else
       System.out.println(abbrev.toUpperCase() + " can be formed in " + numAbbr + " ways");
     return;
   }

   // Another base case -- exactly one word in the phrase:
   if (numWords == 1) {
     numAbbr = occurs(abbrev,0,k-1,phrase[0],0,phrase[0].length()-1);
     if (numAbbr == 0)
       System.out.println(abbrev.toUpperCase() + " is not a valid abbreviation");
     else
       System.out.println(abbrev.toUpperCase() + " can be formed in " + numAbbr + " ways");
     return;
   }

   // General case:
   int first[] = new int[k-numWords+1]; // counts prefixes of abbrev in first
                                        // word of the phrase
   int last[] = new int[k-numWords+1]; // counts suffixes of abbrev occurring
                                       // in last word of the phrase

   // counts internal substrings of abbrev occurring in all but the first
   // and last words: inter[i][j][l] is number of occurrences of a
   // particular substring of abbrev of length l-j+1 in the (i+1)st word
   // of the phrase:
   int inter[][][] = new int[numWords-2][k-numWords+1][k-numWords+1];

   for (int i = 0; i < k-numWords+1; i++)
     first[i] = occurs(abbrev,0,i,phrase[0],0,phrase[0].length()-1);

// DEBUG:
//  for (int i = 0; i < k-numWords+1; i++)
//    System.out.println(abbrev.substring(0,i+1) + " occurs in " +
//                       phrase[0] + " " + first[i] + " times.");

   for (int i = 0; i < k-numWords+1; i++)
     last[i] = occurs(abbrev,numWords+i-1,k-1,phrase[numWords-1],0,
                      phrase[numWords-1].length()-1);

// DEBUG:
//  for (int i = 0; i < k-numWords+1; i++)
//    System.out.println(abbrev.substring(numWords+i-1,k) + " occurs in "
//                       + phrase[numWords-1] + " " + last[i] + " times.");

   for (int i = 0; i < numWords-2; i++) {
     for(int j = 0; j < k-numWords+1; j++) {
       for(int l = j; l < k-numWords+1; l++) {
         inter[i][j][l] = occurs(abbrev,i+j+1,i+l+1,
                                 phrase[i+1],0,phrase[i+1].length()-1);
       }
     }
   }

// DEBUG:
//  for (int i = 0; i < numWords-2; i++) {
//    System.out.println(phrase[i+1]+":");
//    for(int j = 0; j < k-numWords+1; j++) {
//      for (int l = 0; l < j; l++)
//         System.out.print("\t");
//
//      for(int l = j; l < k-numWords+1; l++) {
//         System.out.print(inter[i][j][l]+"\t");
//      }
//      System.out.println();
//    }
//  }

   // Now put it all together using matrix multiplication:
   int temp[] = new int[k-numWords+1];

   // Save current vector:
   for (int i = 0; i < k-numWords+1; i++)
     temp[i] = first[i];

   for (int i = 0; i < numWords-2; i++) {
      for (int j = 0; j < k-numWords+1; j++) {
        // Overwrite current vector with result of multiplication:
        first[j] = 0;
        for (int l = 0; l <= j; l++) {
          first[j] += temp[l] * inter[i][l][j];
        }
      }

      // Save current vector:
      for (int j = 0; j < k-numWords+1; j++)
        temp[j] = first[j];
   }

   // Final step: multiply by the vector containing number of suffixes:
   for (int i = 0; i < k-numWords+1; i++)
     numAbbr += first[i] * last[i];

   if (numAbbr == 0)
     System.out.println(abbrev.toUpperCase() + " is not a valid abbreviation");
   else
     System.out.println(abbrev.toUpperCase() + " can be formed in " +
                        numAbbr + " ways");
 }

 // Get the next insignificant word from the input:
 public static String nextWord() throws IOException {

   while (!tok.hasMoreTokens()) {
     tok = new StringTokenizer(in.readLine());
   }
   return tok.nextToken();
 }

 // Search for all occurrences of w[i] w[i+1] ... w[j] inside
 // x[k] x[k+1] ... x[l]:

 public static int occurs(String w, int i, int j,
                          String x, int k, int l) {
   // Easy base case: first string is empty
   if (j < i)
     return 1;

   // Easy base case: second string is too short to hold first string:
   if (l-k < j-i)
      return 0;

   // Prepare to look up in table:
   String a = w.substring(i,j+1);
   String b = x.substring(k,l+1);
   Integer temp = (Integer)(lookup.get(a+","+b));

   // Found it -- we've already searched for this string:
   if (temp != null) {
      return temp.intValue();
   }

   // Didn't find it, so match first letters and use recursion:
   int count = 0;
   for (int r = k; r <= l; r++)
      if (w.charAt(i) == x.charAt(r)) {
        int t = occurs(w,i+1,j,x,r+1,l);
        count += t;
      }
   a = w.substring(i,j+1);
   b = x.substring(k,l+1);

   // Save in table for future lookups:
   lookup.put(a+","+b,new Integer(count));
   return count;
 }
}