Во время проведения новогодней акции в группе «Бары Судиславля» были разыграны n промокодов. Каждый промокод состоит из ровно шести цифр и даёт право на один бесплатный коктейль в баре «Приют комара». Разумеется, все промокоды различны.
Поскольку «Приют комара» открывается только в 9, а вечеринки в Судиславле, как правило, начинаются уже в 6, то у многих могут возникнуть проблемы с тем, чтобы вбить промокод без ошибок. Необходимо вычислить такое максимальное k, что промокод может быть однозначно идентифицирован, если был введён не более чем с k ошибками. При этом k = 0 означает, что промокоды необходимо вводить абсолютно точно.
Ошибкой в этой задаче следует считать ввод неправильной цифры. Например, значение «123465» содержит две ошибки относительно промокода «123456». Независимо от количества ошибок, введённое значение состоит ровно из шести цифр.
Выходные данные
Выведите максимальное k (разумеется, не превосходящее длины промокода), такое что любой промокод может быть однозначно идентифицирован, если введён с не более чем k ошибками.
Примечание
В первом примере k < 3, так как если посетитель бара вобьёт значение «090909», то будет невозможно определить, какой именно промокод ему соответствует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
000000
999999
|
2
|
|
2
|
6
211111
212111
222111
111111
112111
121111
|
0
|