Edward는 시장에서 가장 안전한 금고를 제조하는 회사 Enigma의 창립자이자 대표입니다. Enigma 금고는 5자리 비밀번호를 사용하는 다이얼 자물쇠로 보호됩니다. 이 자물쇠는 다섯 개의 바퀴와 "열기" 버튼으로 구성되어 있습니다. 각 바퀴에는 0부터 9까지의 모든 숫자가 이 순서대로 적혀 있으며, 숫자 9 다음에는 다시 숫자 0이 나타납니다.

한 번의 연산은 임의의 바퀴 하나를 어느 한쪽 방향으로 한 칸 회전시키는 것으로 정의됩니다(예: 숫자 9를 8 또는 0으로 바꾸기). 두 비밀번호 사이의 거리는 입력된 한 비밀번호를 다른 비밀번호로 바꾸기 위해 필요한 최소 연산 횟수입니다. 예를 들어, 38911과 68000 사이의 거리는 $3 + 0 + 1 + 1 + 1 = 6$입니다.

금고 제조사들은 가장 흔히 사용되는 비밀번호의 통계를 보유하고 있으며, 가장 인기 있는 것부터 순서대로 $n$개의 비밀번호가 주어집니다. Enigma는 유연성을 자랑합니다 — 각 고객은 가장 인기 있는 $n$개의 비밀번호 중 상위 몇 개를 피할지 선택할 수 있습니다. 그러면 Edward는 가장 인기 있는 비밀번호 수열의 선택된 접두사에 속한 비밀번호들까지의 최소 거리를 최대화하는 비밀번호를 선택합니다.

1부터 $n$까지의 각 $k$에 대해, 어떤 비밀번호에서 가장 인기 있는 상위 $k$개의 비밀번호 중 가장 가까운 것까지의 최대 가능 거리를 구하고, 그러한 거리를 달성하는 비밀번호의 개수를 세어 주세요.

입력

첫 번째 줄에 인기 있는 비밀번호의 개수를 나타내는 정수 $n$ ($1 \le n \le 99\,999$)이 주어집니다.

다음 $n$개의 줄에는 각각 0–9의 숫자 5개로 이루어진 문자열이 주어지며, 앞에 0이 포함될 수 있습니다. 이는 가장 인기 있는 것부터 순서대로 나열된 비밀번호들입니다. 모든 비밀번호는 서로 다릅니다.

출력

$n$개의 줄을 출력합니다. $k$번째 줄에는 공백으로 구분된 두 정수를 출력해야 하며, 이는 상위 $k$개의 가장 인기 있는 비밀번호 중 가장 가까운 비밀번호까지의 최대 가능 거리와 그 거리를 가지는 비밀번호의 개수입니다.

예제

예제 입력 1

3
00000
00001
12345

예제 출력 1

25 1
24 2
17 270

예제 입력 2

3
12345
23456
67890

예제 출력 2

25 1
22 20
12 15270

노트

$k = 1$일 때, 비밀번호 00000으로부터의 최대 가능 거리는 25이며, 오직 비밀번호 55555에 의해서만 달성됩니다.

$k = 2$일 때, 비밀번호 00000과 00001 중 더 가까운 것까지의 최대 가능 거리는 24이며, 두 비밀번호 55555와 55556에 의해 달성됩니다. 첫 번째는 00001로부터 거리가 24이고, 두 번째는 00000으로부터 거리가 24입니다.

$k = 3$일 때, 비밀번호 00000, 00001, 12345 중 가장 가까운 것까지의 최대 가능 거리는 17이며, 예를 들어 55570과 55580을 포함한 270개의 서로 다른 비밀번호에 의해 달성됩니다. 첫 번째는 12345로부터 거리가 17이고, 두 번째는 00000으로부터 거리가 17입니다.