Edward là người sáng lập và đứng đầu công ty Enigma, nhà sản xuất những chiếc két sắt an toàn nhất trên thị trường. Két sắt Enigma được bảo vệ bởi một ổ khóa số với mã gồm 5 chữ số. Ổ khóa bao gồm năm bánh xe và một nút "mở". Mỗi bánh xe chứa tất cả các chữ số từ 0 đến 9 (theo thứ tự này); sau chữ số 9, chữ số 0 lại xuất hiện.

Một thao tác được định nghĩa là xoay bất kỳ bánh xe nào một nấc theo một trong hai chiều, ví dụ đổi chữ số 9 thành 8 hoặc 0. Khoảng cách giữa hai mã là số thao tác tối thiểu cần thiết để biến đổi một mã đã nhập thành mã kia. Ví dụ, khoảng cách giữa 38911 và 68000 là $3 + 0 + 1 + 1 + 1 = 6$.

Các nhà sản xuất két sắt lưu giữ thống kê về những mã được sử dụng phổ biến nhất — bạn được cho $n$ mã như vậy theo thứ tự từ phổ biến nhất đến ít phổ biến nhất. Enigma tự hào về sự linh hoạt — mỗi khách hàng có thể chọn số lượng mã trong số $n$ mã phổ biến nhất mà họ muốn tránh. Sau đó, Edward chọn một mã sao cho khoảng cách nhỏ nhất từ mã đó đến các mã trong tiền tố đã chọn của dãy các mã phổ biến nhất đạt giá trị lớn nhất.

Với mỗi $k$ từ 1 đến $n$, nhiệm vụ của bạn là tìm khoảng cách lớn nhất có thể từ một mã nào đó đến mã gần nhất trong số $k$ mã phổ biến nhất, và đếm xem có bao nhiêu mã đạt được khoảng cách như vậy.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 99\,999$), biểu thị số lượng mã phổ biến.

Mỗi dòng trong $n$ dòng tiếp theo chứa một xâu gồm 5 chữ số 0–9, có thể có các chữ số 0 ở đầu. Đây là các mã phổ biến theo thứ tự từ phổ biến nhất đến ít phổ biến nhất. Tất cả các mã đều đôi một phân biệt.

Kết quả

In ra $n$ dòng; dòng thứ $k$ gồm hai số nguyên cách nhau bởi dấu cách — khoảng cách lớn nhất có thể đến mã gần nhất trong số $k$ mã phổ biến nhất, và số lượng mã có khoảng cách đó.

Ví dụ

Dữ liệu vào 1

3
00000
00001
12345

Kết quả 1

25 1
24 2
17 270

Dữ liệu vào 2

3
12345
23456
67890

Kết quả 2

25 1
22 20
12 15270

Ghi chú

Với $k = 1$, khoảng cách lớn nhất có thể từ mã 00000 là 25, chỉ đạt được bởi mã 55555.

Với $k = 2$, khoảng cách lớn nhất có thể đến mã gần hơn trong hai mã 00000 và 00001 là 24, đạt được bởi hai mã: 55555 và 55556. Mã thứ nhất cách 00001 một khoảng bằng 24, và mã thứ hai cách 00000 một khoảng bằng 24.

Với $k = 3$, khoảng cách lớn nhất có thể đến mã gần nhất trong các mã 00000, 00001 và 12345 là 17, đạt được bởi 270 mã khác nhau, ví dụ 55570 và 55580. Mã thứ nhất cách 12345 một khoảng bằng 17, và mã thứ hai cách 00000 một khoảng bằng 17.