Fuzzy Dictionary Query

Given a dictionary of words and a query string, implement a fuzzy query component for an electronic dictionary. The edit distance between two strings \(a\) and \(b\) is defined as the minimum number of operations required to transform one string into the other, where an operation is one of the following:

• Delete a character from a string.
• Insert a character into a string.
• Replace a character in a string with another character.

Your task is to process a query string as follows:

1. If the query string exists in the dictionary, output \(-1\).
2. If the query string is not in the dictionary, count and output the number of words in the dictionary whose edit distance to the query string is exactly \(1\).

Note: Two strings have an edit distance of 1 if and only if one single operation (insert, delete, or substitute) can convert one string into the other.

inputFormat

The first line contains an integer \(n\) representing the number of words in the dictionary. The following \(n\) lines each contain a word. The last line contains the query string.

Example:

3
apple
apply
orange
applo

outputFormat

If the query string exists in the dictionary, output \(-1\). Otherwise, output the count of dictionary words that have an edit distance of exactly \(1\) from the query string.

sample

3
apple
apply
orange
apple

-1