The Hamming distance between two strings a and b of equal length is the number of positions where the strings differ.

You are given n bit strings, each of length k and your task is to calculate the minimum Hamming distance between two strings.

Input

The first input line has two integers n and k: the number of bit strings and their length.

Then there are n lines each consisting of one bit string of length k.

Output

Print the minimum Hamming distance between two strings.

Constraints

• 2 \le n \le 2 \cdot 10^4
• 1 \le k \le 30

Example

Input:

5 6
110111
001000
100001
101000
101110

Output:

1

Explanation: The strings 101000 and 001000 differ only at the first position.