Minimum Transformations

Given a string S and a dictionary of words, determine the minimum number of single-character transformations needed to convert S into one of the dictionary words. In each transformation, you may change exactly one character in S to any other character. All dictionary words are guaranteed to have the same length as S.

The transformation count between two strings is equivalent to the Hamming distance, which is defined as:

$$\text{Hamming}(s, w) = \sum_{i=1}^{n} [s_i \neq w_i] $$

Your task is to compute the minimum Hamming distance between the given string and any word in the dictionary.

inputFormat

The input is read from standard input and is formatted as follows:

• The first line contains the string S.
• The second line contains an integer N representing the number of words in the dictionary.
• The following N lines each contain a dictionary word.

outputFormat

The output is a single integer written to standard output, representing the minimum number of transformations needed to convert S into some word in the dictionary.

## sample

abc
3
adc
bcc
aeb

1