Edward is the founder and head of the company Enigma, the manufacturer of the most secure safes on the market. Enigma safes are protected by a combination lock with a 5-digit code. The lock consists of five wheels and an "open" button. Each wheel contains all digits from 0 to 9 (in this order); after the digit 9, the digit 0 appears again.

An operation is defined as rotating any wheel by one position in either direction, for example changing the digit 9 to 8 or 0. The distance between two codes is the minimum possible number of operations required to change one entered code into the other. For example, the distance between 38911 and 68000 is $3 + 0 + 1 + 1 + 1 = 6$.

Safe manufacturers keep statistics of the most commonly used codes — you are given $n$ such codes in order from most to least popular. Enigma prides itself on flexibility — each client can choose how many of the $n$ most popular codes they wish to avoid. Edward then chooses a code that maximizes the smallest distance to the codes from the selected prefix of the sequence of the most popular codes.

For each $k$ from 1 to $n$, your task is to find the largest possible distance of some code to the closest among the $k$ most popular codes, and count how many codes achieve such a distance.

Input

The first line contains an integer $n$ ($1 \le n \le 99\,999$), denoting the number of popular codes.

Each of the following $n$ lines contains a string consisting of 5 digits 0–9, possibly with leading zeros. These are the popular codes in order from most to least popular. All codes are pairwise distinct.

Output

Output $n$ lines; the $k$-th line should contain two integers separated by a space — the largest possible distance to the nearest code among the $k$ most popular ones, and the number of codes with that distance.

Examples

Input 1

3
00000
00001
12345

Output 1

25 1
24 2
17 270

Input 2

3
12345
23456
67890

Output 2

25 1
22 20
12 15270

Note

For $k = 1$, the largest possible distance from code 00000 is 25, achieved only by the code 55555.

For $k = 2$, the largest possible distance to the nearer of the codes 00000 and 00001 is 24, achieved by two codes: 55555 and 55556. The first is 24 away from 00001, and the second is 24 away from 00000.

For $k = 3$, the largest possible distance to the nearest among the codes 00000, 00001, and 12345 is 17, achieved by 270 different codes, for example 55570 and 55580. The first is 17 away from 12345, and the second is 17 away from 00000.