Stepan has a set of n strings. Also, he has a favorite string s.
Stepan wants to do the following. He will take some strings of his set and write them down one after another. It is possible that he will take some strings more than once, and will not take some of them at all.
Your task is to determine the minimum number of strings in the set which Stepan needs to take and write so that the string s appears as a subsequence in the resulting written down string.
For example, in the string "abcd" strings "ad", "acd", "abcd" appear as subsequences, and strings "ba", "abdc" don't appear as subsequences.
Output
Print the minimum number of strings which Stepan should take from the set and write them down one after another so that the string
s appears as a subsequence in the resulting written down string. Each string from the set should be counted as many times as Stepan takes it from the set.
If the answer doesn't exsist, print
-1.
Note
In the first test, Stepan can take, for example, the third and the second strings from the set, write them down, and get exactly his favorite string.
In the second example Stepan can take, for example, the second, the third and again the second strings from the set and write them down. Then he will get a string "
aabaaaab", in which his favorite string "
baaab" is a subsequence.
In the third test Stepan can not get his favorite string, because it contains the letter "
c", which is not presented in any of the strings in the set.