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
////////////////////////////////////////
///  tu3 pro-con template            ///
////////////////////////////////////////
#include "bits/stdc++.h"
using namespace std;

// -- loop macros -- //
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i,n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i,s,n) for (int i = (int)(s); i < (n); i++)
#define RFOR(i,s,n) for (int i = (n)-1; i >= (s); i--)
#define FOREACH(i,container) for (auto &&i : container)
#define allof(c) c.begin(), c.end()
#define partof(c,i,n) c.begin() + (i), c.begin() + (i) + (n)

// -- functors -- //
#define PREDICATE(t,a,exp) [&](const t & a) -> bool { return exp; }
#define COMPARISON(t,a,b,exp) [&](const t & a, const t & b) -> bool { return exp; }

#define PRED(a,exp) [&](const auto & a) -> bool { return exp; }
#define COMP(a,b,exp) [&](const auto & a, const auto & b) -> bool { return exp; }
#define CONV1(a,exp) [&](const auto & a) -> auto { return exp; }
#define CONV2(a,b,exp) [&](const auto & a, const auto & b) -> auto { return exp; }
#define CONV3(a,b,c,exp) [&](const auto & a, const auto & b, const auto & c) -> auto { return exp; }

// -- typedefs -- //
#define EPS 1e-9

typedef unsigned int uint;
typedef long long llong;
typedef unsigned long long ullong;

// -- I/O Helper -- //
struct _Reader { _Reader(istream &cin) :cin(cin) {} istream &cin; template <class T> _Reader operator ,(T &rhs) { cin >> rhs; return *this; } };
struct _Writer { _Writer(ostream &cout) :cout(cout) {} ostream &cout; bool f{ false }; template <class T> _Writer operator ,(const T &rhs) { cout << (f ? " " : "") << rhs; f = true; return *this; } };
#define READ(t,...) t __VA_ARGS__; (_Reader{cin}), __VA_ARGS__
#define WRITE(...) (_Writer{cout}), __VA_ARGS__; cout << '\n'
#define DEBUG(...) (_Writer{cerr}), __VA_ARGS__; cerr << '\n'

// -- vevector -- //
template <class T> struct vevector : public vector<vector<T>> { vevector(size_t n = 0, size_t m = 0, const T &initial = T()) : vector<vector<T>>(n, vector<T>(m, initial)) { } };
template <class T> struct vevevector : public vector<vevector<T>> { vevevector(size_t n = 0, size_t m = 0, size_t l = 0, const T &initial = T()) : vector<vevector<T>>(n, vevector<T>(m, l, initial)) { } };
template <class T> struct vevevevector : public vector<vevevector<T>> { vevevevector(size_t n = 0, size_t m = 0, size_t l = 0, size_t k = 0, const T &initial = T()) : vector<vevevector<T>>(n, vevevector<T>(m, l, k, initial)) { } };

namespace std {
	template <class T1, class T2> inline istream & operator >> (istream & in, pair<T1, T2> &p) { in >> p.first >> p.second; return in; }
	template <class T1, class T2> inline ostream & operator << (ostream &out, const pair<T1, T2> &p) { out << p.first << " " << p.second; return out; }
}

template <class T> T read() { T t; cin >> t; return t; }
template <class T> vector<T> read(int n) { vector<T> v; REP(i, n) { v.push_back(read<T>()); } return v; }
template <class T> vevector<T> read(int n, int m) { vevector<T> v; REP(i, n) v.push_back(read<T>(m)); return v; }
template <class T> vector<T> readjag() { return read<T>(read<int>()); }
template <class T> vevector<T> readjag(int n) { vevector<T> v; REP(i, n) v.push_back(readjag<T>()); return v; }

template <class T> struct iter_pair_t { T beg, end; };
template <class T> iter_pair_t<T> iter_pair(T beg, T end) { return iter_pair_t<T>{beg, end}; }
template <class T> ostream & operator << (ostream &out, iter_pair_t<T> v) { if (v.beg != v.end) { out << *v.beg++; while (v.beg != v.end) { out << " " << *v.beg++; } } return out; }
template <class T1> ostream & operator << (ostream &out, const vector<T1> &v) { return out << iter_pair(begin(v), end(v)); }

// -- etc -- //
template <class T> T infinity_value();
#define DEFINE_INFINITY_VALUE(T, val) template <> constexpr T infinity_value<T>() { return (val); }
DEFINE_INFINITY_VALUE(int, 1 << 28);
DEFINE_INFINITY_VALUE(uint, 1u << 28);
DEFINE_INFINITY_VALUE(llong, 1ll << 60);
DEFINE_INFINITY_VALUE(ullong, 1ull << 60);
DEFINE_INFINITY_VALUE(double, HUGE_VAL);
DEFINE_INFINITY_VALUE(float, HUGE_VAL);
#define INF(T) infinity_value<T>()

inline int sign_of(double x) { return (abs(x) < EPS ? 0 : x > 0 ? 1 : -1); }
template <class TInt> bool in_range(TInt val, TInt min, TInt max) { return val >= min && val < max; }
template <> bool in_range<double>(double val, double min, double max) { return val - min > -EPS && val - max < EPS; }
template <> bool in_range<float>(float val, float min, float max) { return val - min > -EPS && val - max < EPS; }
template <class TInt> bool in_range2d(TInt x, TInt y, TInt w, TInt h) { return x >= 0 && x < w && y >= 0 && y < h; }
vector<int> iotavn(int start, int count) { vector<int> r(count); iota(allof(r), start);	return r; }

// 文字列の分割
vector<string> split(const string &str, const string &s, bool removeEmpty = false)
{
	vector<string> ret;
	size_t p = 0, sl = s.size();
	while (true)
	{
		size_t q = str.find(s, p);
		if (q == str.npos) break;
		ret.push_back(str.substr(p, q - p));
		p = q + sl;
	}
	ret.push_back(str.substr(p));
	if (removeEmpty) ret.erase(remove(allof(ret), string()), ret.end());
	return ret;
}

//// start up ////
void solve();
int main()
{
	//// for local debugging
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	//auto classic_table = ctype<char>::classic_table();
	//vector<ctype<char>::mask> ctable(classic_table, classic_table + ctype<char>::table_size);
	//ctable[':'] |= ctype_base::space; // as delimitor
	//ctable[','] |= ctype_base::space; // as delimitor
	//cin.imbue(locale(cin.getloc(), new ctype<char>(ctable.data())));

	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed;
	cout << setprecision(std::numeric_limits<double>::max_digits10);
	solve();

	return 0;
}

////////////////////
/// template end ///
////////////////////

// 文字列の置換
void inplaceReplace(string &target, const string &from, const string &to, bool global = false)
{
	string::size_type p = 0;
	do
	{
		string::size_type pos = target.find(from, p);
		if (pos == target.npos) { break; }
		target.replace(pos, from.length(), to);
		p = pos + to.length();
	} while (global);
}

void solve()
{
	while (true)
	{
		READ(int, N);
		if (!N) { break; }
		auto subst = read < pair<string, string> >(N);
		READ(string, g, d);

		map<string, int> a;
		queue<pair<string, int>> q;
		q.push({ g,0 });
		while (!q.empty())
		{
			auto p = q.front(); q.pop();
			//DEBUG(p.first);
			FOREACH(s, subst)
			{
				auto n = p.first;
				inplaceReplace(n, s.first, s.second, true);
				
				if (n.size() <= d.size() && !a.count(n))
				{
					a[n] = p.second + 1;
					q.push({ n, p.second + 1 });
				}
				if (n == d) { break; }
			}
		}
		WRITE( a.count(d) ? a[d] : -1);
	}
}

