// Arup Guha
// 9/22/2011
// Solution to COT 4210 Program #1: Chomsky Normal Form Grammars

// Edited on 6/28/2012 to be solution to 2008 Southeast Regional Problem J: Worms

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

class Variable {

	public Character letter;
	public ArrayList<String> splitRules;

	public Variable(char c) {
		letter = c;
		splitRules = new ArrayList<String>();
	}

	public void addRule(String s) {
		splitRules.add(s);
	}

}
public class j {

	private int numVars;
	private Variable[] vars;

	// Sets up this grammar.
	public j(Scanner fin, int numRules) {

		// Valid letters in problem statement - 'A' through 'T'
		numVars = 20;
		vars = new Variable[numVars];

		// Add all variables A - T
		for (int i=0; i<20; i++)
			vars[i] = new Variable((char)('A'+i));

		// Set up each rule.
		for (int i=0; i<numRules; i++) {
			String rule = fin.next();
			int index = get(vars, rule.charAt(0));
			vars[index].addRule(rule.substring(1));
		}
	}

	// Find the variable in list that matches c.
	public static int get(Variable[] list, char c) {

		// Go through the list to find it.
		for (int i=0; i<list.length; i++)
			if (list[i].letter == c)
				return i;

		// Not found.
		return -1;
	}

	// Returns the index at which the variable c is stored.
	// If c is not a variable in this grammar, -1 is returned.
	public int getIndex(char c) {

		// Look for c. If found, return the corresponding index.
		for (int i=0; i<vars.length; i++)
			if (vars[i].letter == c)
				return i;

		// Not found as a variable.
		return -1;
	}

	public int minDerivation(String s) {

		// Use variable names given in the CYK algorithm (Wikipedia).
		int n = s.length();
		int r = numVars;

		int[][][] canCreate = new int[n][n][r];

		// 100 means we can't do the derivation.
		for (int i=0; i<n; i++)
			for (int j=0; j<n; j++)
				for (int k =0; k<r; k++)
					canCreate[i][j][k] = 100;

		// Loop through each position in the string S.
		for (int i=0; i<n; i++) {
			for (int j=0; j<r; j++) {
				if (s.charAt(i) == vars[j].letter)
					canCreate[i][0][j] = 0;
			}
		}

		// i+1 represents the length of the substrings we are currently checking.
		for (int i=1; i<n; i++) {

			// The starting index of the substring in the big string.
			for (int j=0; j<n-i; j++) {

				// Possible split points for the span.
				for (int k=0; k<=i-1; k++) {

					// Go through each variable.
					for (int x=0; x<vars.length; x++) {

						// Go through each rule for this variable.
						for (String rule: vars[x].splitRules) {

							int LHS = getIndex(vars[x].letter);
							int RHS_1 = getIndex(rule.charAt(0));
							int RHS_2 = getIndex(rule.charAt(1));

							int tempval = Math.max(canCreate[j][k][RHS_1], canCreate[j+k+1][i-k-1][RHS_2]) + 1;
							if (tempval < canCreate[j][i][LHS])
								canCreate[j][i][LHS] = tempval;
						}
					}
				}
			}
		}

		// Find the minimum derivation length of this string.
		int ans = 100;
		for (int i=0; i<r; i++)
			if (canCreate[0][n-1][i] < ans)
				ans = canCreate[0][n-1][i];

		// Remained unsolved.
		if (ans == 100) ans = -1;

		return ans;
	}

	public static void main(String[] args) throws Exception {

		Scanner stdin = new Scanner(System.in);

		// Go through each case.
		int numRules = stdin.nextInt();
		while (numRules != 0) {

			// Test this string and output the answer.
			j thisGrammar = new j(stdin, numRules);
			String test = stdin.next();
			System.out.println(thisGrammar.minDerivation(test));
			numRules = stdin.nextInt();
		}
	}
}