Do you know "sed," a tool provided with Unix? Its most popular use is to substitute every occurrence of a string  contained in the input string (actually each input line) with another string β. More precisely, it proceeds as follows.

1. Within the input string, every non-overlapping (but possibly adjacent) occurrences of α are marked. If there is more than one possibility for non-overlapping matching, the leftmost one is chosen.
2. Each of the marked occurrences is substituted with β to obtain the output string; other parts of the input string remain intact.



For example, when α is "aa" and β is "bca", an input string "aaxaaa" will produce "bcaxbcaa", but not "aaxbcaa" nor "bcaxabca". Further application of the same substitution to the string "bcaxbcaa" will result in "bcaxbcbca", but this is another substitution, which is counted as the second one.

In this problem, a set of substitution pairs (αi, βi) (i = 1, 2, ... , n), an initial string γ, and a final string δ are given, and you must investigate how to produce δ from γ with a minimum number of substitutions. A single substitution (αi, βi) here means simultaneously substituting all the non-overlapping occurrences of αi, in the sense described above, with βi.

You may use a specific substitution (αi, βi ) multiple times, including zero times.



Input

The input consists of multiple datasets, each in the following format.

n
α1 β1
α2 β2
.
.
.
αn βn
γ δ

n is a positive integer indicating the number of pairs. αi and βi are separated by a single space. You may assume that 1 ≤ |αi| < |βi| ≤ 10 for any i (|s| means the length of the string s), αi ≠ αj for any i ≠ j, n ≤ 10 and 1 ≤ |γ| < |δ| ≤ 10. All the strings consist solely of lowercase letters. The end of the input is indicated by a line containing a single zero.

Output

For each dataset, output the minimum number of substitutions to obtain δ from γ. If δ cannot be produced from γ with the given set of substitutions, output -1.

Example

Input

2
a bb
b aa
a
bbbbbbbb
1
a aa
a
aaaaa
3
ab aab
abc aadc
ad dee
abc
deeeeeeeec
10
a abc
b bai
c acf
d bed
e abh
f fag
g abe
h bag
i aaj
j bbb
a
abacfaabe
0


Output

3
-1
7
4
import java.io.*;
import java.util.*;
import java.lang.ArrayIndexOutOfBoundsException;
import java.math.BigInteger;

/**
 * @author yoshikyoto
 */
class Main {
	public static void main(String[] args) throws Exception {
		// System.out.println("aaxaaa".replaceAll("aa", "cba"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			int n = Integer.parseInt(br.readLine());
			if(n == 0) break;
			String[][] sed = new String[n][];
			for(int i = 0; i < n; i++){
				sed[i] = br.readLine().split(" ");
			}
			// ゴール
			String s = br.readLine();
			String g = br.readLine();
			System.out.println(bfs(s, g, sed));
		}
	}
	
	static int bfs(String s, String g, String[][] sed){
		if(s.equals(g)) return 0;
		int n = sed.length;
		
		// 最初の状態
		State startState = new State(s, 0);
		ArrayDeque<State> q = new ArrayDeque<State>();
		q.addLast(startState);
		// 幅優先探索
		while(q.size() > 0) {
			State state = q.pollFirst();
			for (int i = 0; i < n; i++) {
				String newStr = state.str.replaceAll(sed[i][0], sed[i][1]);
				if(newStr.equals(g)) {
					return state.count + 1;
				}
				if(newStr.length() < g.length() && !newStr.equals(state.str)) {
					q.addLast(new State(newStr, state.count + 1));
				}
			}
		}
		return -1;
	}
}

class State {
	String str;
	int count;
	public State(String str, int count) {
		this.str = str;
		this.count = count;
	}
}

/**
 * 複素数
 */
class Complex {
	static Complex I = new Complex(0, 1);
	
	double r = 0.0;
	double i = 0.0;
	Complex(double r, double i) {
		this.r = r;
		this.i = i;
	}
	
	/**
	 * 和
	 */
	public Complex add(Complex a) {
		return new Complex(r * a.r, i + a.i);
	}
	
	/**
	 * 積
	 */
	public Complex mul(Complex a) {
		return new Complex(
				r * a.r - i * a.i,
				r * a.i + i * a.r);
	}
	
	public Complex divide(double a) {
		return new Complex(r/a, i/a);
	}
	
	public Complex inverse() {
		double b = 1 / (r*r + i*i);
		return new Complex(r/b, -i/b);
	}
	    

	@Override
	public String toString(){
		return r + "+" + i + "i";
	}
}




// --- ここから下はライブラリ ----------
/**
 * MyUtil
 * @author yoshikyoto
 */
class MyIO {
	public static int toInt(boolean[] a){
		int pow = 1, ret = 0, l = a.length;
		for(int i = 0; i < l; i++){
			if(a[i]) ret += pow;
			pow *= 2;
		}
		return ret;
	}
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static int ins[];
	public static int[] readIntMap() throws IOException{return parseInt(readLine().split(" "));}
	public static int readIntMap(int i) throws Exception{
		if(i == 0) ins = readIntMap();
		return ins[i];
	}
	public static int[][] readIntMap(int n, int m) throws IOException{
		int[][] ret = new int[n][];
		for(int i = 0; i < n; i++) ret[i] = readIntMap();
		return ret;
	}
	public static int[] readIntToMap(int n) throws IOException{
		int[] ret = new int[n];
		for(int i = 0; i < n; i++) ret[i] = readInt();
		return ret;
	}
	public static int[] readNoDistIntMap() throws IOException{
		String[] strs = readLine().split("");
		int l = strs.length;
		int[] ret = new int[l-1];
		for(int i = 1; i < l; i++)
			ret[i-1] = parseInt(strs[i]);
		return ret;
	}
	public static String readLine() throws IOException{return br.readLine();}
	public static int readInt() throws IOException{return Integer.parseInt(br.readLine());}
	public static int[] parseInt(String[] arr){
		int[] res = new int[arr.length];
		for(int i = 0; i < arr.length; i++)res[i] = Integer.parseInt(arr[i]);
		return res;
	}
	public static double[] parseDouble(String[] arr){
		double[] res = new double[arr.length];
		for(int i = 0; i < arr.length; i++)res[i] = Double.parseDouble(arr[i]);
		return res;
	}
	public static boolean[] parseBool(String[] arr){
		int[] t = parseInt(arr);
		boolean[] res = new boolean[t.length];
		for(int i = 0; i < t.length; i++){
			if(t[i] == 1){res[i] = true;
			}else{res[i] = false;}
		}
		return res;
	}
	public static int parseInt(Object o){
		return Integer.parseInt(o.toString());
	}
}