Farmer John 的 $N$ ($1 \leq N \leq 10^5$) 头奶牛每头都有一个以位串（由字符 '0' 和 '1' 组成的字符串）形式表示的农场 ID。最年长的奶牛 Bessie 记住了所有奶牛的农场 ID，并喜欢四处询问奶牛们的 ID。

当一头奶牛被问及她的农场 ID 时，她会开始说出正确的位串，但可能会感到困惑并在说完整之前停下来。当 Bessie 听到这个位串时，如果它不是农场中任何一头奶牛的农场 ID，她就会耸耸肩走开。然而，如果它是除被询问的那头奶牛之外的另一头奶牛的 ID，她就会认为发生了身份盗用，并对农场实施封锁。注意，即使奶牛说出了完整的农场 ID，这种情况也可能发生。

Farmer John 希望防止这种情况发生，并愿意通过在奶牛的农场 ID 后添加更多位来更改它们。在一秒钟内，他可以在任何一头奶牛的农场 ID 末尾添加一个位。请计算他防止封锁发生所需的最短时间。

输入格式

第一行包含 $N$，即 Farmer John 农场中奶牛的数量。

接下来 $N$ 行，第 $k$ 行包含第 $k$ 头奶牛的农场 ID 位串。

没有奶牛的农场 ID 为空，且所有农场 ID 的总长度最多为 $10^6$。

输出格式

输出 Farmer John 为确保永远不会发生封锁所需花费的最短秒数。

样例

样例输入 1

3
1
1
1

样例输出 1

5

说明 1

我们可以通过在第一个农场 ID 后添加 '0'，在第二个后添加 '10'，在第三个后添加 '11'，使农场 ID 变为 '10'、'110' 和 '111'，从而在 5 秒内使封锁变得不可能。

可以证明这无法在 4 秒或更短时间内完成。例如，如果保持原样，那么所有 3 头奶牛都有相同的农场 ID '1'，因此当 Bessie 听到它时，它总是另一头奶牛的农场 ID。

作为另一个例子，如果你只花费 2 秒在第二个农场 ID 后添加 '0'，在第三个后添加 '1'，那么农场 ID 为 '1'、'10' 和 '11'，因此第二头和第三头奶牛在说出她们的农场 ID 时，可能会在中途停下只说出 '1'，这会是第一头奶牛的农场 ID。

样例输入 2

3
1
11
111

样例输出 2

2

说明 2

我们可以通过在头两个农场 ID 后添加 '0'，使农场 ID 变为 '10'、'110' 和 '111'，从而在 2 秒内使封锁变得不可能。可以证明这无法在 1 秒内完成。

样例输入 3

3
1
1
11

样例输出 3

4

说明 3

我们可以通过在第一个农场 ID 后添加 '00'，在第二个后添加 '01'，从而在 4 秒内使封锁变得不可能。可以证明这无法在 3 秒或更短时间内完成。

样例输入 4

5
0
01
0011
010
01

样例输出 4

6

样例输入 5

14
0
1
1
0
1
0
1
1
1
1
1
0
0
1

样例输出 5

41

子任务

• 输入 6-7：所有农场 ID 的长度均为 $1$。
• 输入 8-15：$N \le 10^2$，且所有农场 ID 的总长度不超过 $10^3$。
• 输入 16-25：无额外限制。