Mingoo đã phát triển một ứng dụng chat thế hệ mới, ChatChatA!

Sau khi triển khai ChatChatA, một báo cáo lỗi nghiêm trọng đã được gửi đến Mingoo! Trong quá trình nhập tin nhắn, khi ký tự cuối cùng của tin nhắn là một ký tự nhất định, nếu nhập một ký tự cụ thể, tin nhắn sẽ bị "nhân đôi"!

Giải thích một cách chính xác, "nhân đôi" có nghĩa như sau:

• Gọi tin nhắn đang được nhập là $M$, ký tự cuối cùng của $M$ là $s$, và ký tự sắp nhập là $c$.
• Gọi tập hợp các cặp $(s, c)$ làm cho tin nhắn "nhân đôi" là $D$.
  • Nếu $(s, c) \in D$, thì khi nhập $c$, $M$ sẽ trở thành $M + M + c$ thay vì $M + c$!
  • Nếu $(s, c) \notin D$, thì khi nhập $c$, $M$ sẽ trở thành $M + c$.
• Nếu $M$ là xâu rỗng, $M$ sẽ không bị "nhân đôi".

Người dùng ChatChatA là Gumingoo muốn biết số thao tác nhập tối thiểu để nhập được xâu $T$.

Ban đầu tin nhắn $M$ là xâu rỗng, và mỗi thao tác nhập là một trong hai hành động sau:

• Thêm ký tự $c$ vào $M$. Theo điều kiện trên, tin nhắn có thể bị "nhân đôi".
• Xóa ký tự cuối cùng của $M$. Chỉ có thể chọn hành động này khi $M$ không phải là xâu rỗng.

Hãy giúp Gumingoo tìm số thao tác nhập tối thiểu để tin nhắn hiện tại $M$ trở thành $T$!

Dữ liệu vào

Dòng đầu tiên chứa kích thước $N$ của $D$. ($1 \le N \le 676 = 26^2$)

Dòng thứ hai chứa xâu $S$ gồm $N$ chữ cái tiếng Anh in thường, dòng thứ ba chứa xâu $C$ gồm $N$ chữ cái tiếng Anh in thường.

Gọi $S_i$ là ký tự thứ $i$ của $S$, $C_i$ là ký tự thứ $i$ của $C$, thì $D=\{(S_i, C_i) : 1 \le i \le N\}$.

$|D|=N$. Nghĩa là, không có cặp $(S_i, C_i)$ nào trùng nhau.

Dòng thứ tư chứa xâu $T$ gồm các chữ cái tiếng Anh in thường cần nhập. ($1 \le |T| \le 500\,000$)

Dữ liệu ra

Dòng đầu tiên in ra số thao tác nhập tối thiểu cần thiết để biến tin nhắn hiện tại thành $T$.

Nếu không thể biến tin nhắn hiện tại thành $T$ thì in ra $-1$.

Ví dụ

Dữ liệu vào 1

1
t
a
chatchata

Dữ liệu ra 1

5

Dữ liệu vào 2

2
ct
ha
chatchata

Dữ liệu ra 2

-1

Dữ liệu vào 3

2
af
bd
aafaaafaafaaafd

Dữ liệu ra 3

8