Edward adalah pendiri dan pimpinan perusahaan Enigma, produsen brankas paling aman di pasaran. Brankas Enigma dilindungi oleh kunci kombinasi dengan kode 5 digit. Kunci tersebut terdiri dari lima roda dan sebuah tombol "buka". Setiap roda memuat semua digit dari 0 hingga 9 (dalam urutan ini); setelah digit 9, digit 0 muncul kembali.

Sebuah operasi didefinisikan sebagai memutar roda mana pun sebanyak satu posisi ke salah satu arah, misalnya mengubah digit 9 menjadi 8 atau 0. Jarak antara dua kode adalah jumlah operasi minimum yang diperlukan untuk mengubah satu kode yang dimasukkan menjadi kode lainnya. Sebagai contoh, jarak antara 38911 dan 68000 adalah $3 + 0 + 1 + 1 + 1 = 6$.

Produsen brankas menyimpan statistik kode yang paling sering digunakan — Anda diberikan $n$ kode semacam itu secara berurutan dari yang paling populer hingga yang paling tidak populer. Enigma membanggakan fleksibilitasnya — setiap klien dapat memilih berapa banyak dari $n$ kode paling populer yang ingin mereka hindari. Edward kemudian memilih sebuah kode yang memaksimumkan jarak terkecil ke kode-kode dari prefiks pilihan pada barisan kode paling populer tersebut.

Untuk setiap $k$ dari 1 hingga $n$, tugas Anda adalah mencari jarak terbesar yang mungkin dari suatu kode ke kode terdekat di antara $k$ kode paling populer, serta menghitung berapa banyak kode yang mencapai jarak tersebut.

Masukan

Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 99\,999$), yang menyatakan banyaknya kode populer.

Masing-masing dari $n$ baris berikutnya berisi sebuah string yang terdiri dari 5 digit 0–9, mungkin dengan nol di depan. Ini adalah kode-kode populer secara berurutan dari yang paling populer hingga paling tidak populer. Semua kode berbeda satu sama lain.

Keluaran

Keluarkan $n$ baris; baris ke-$k$ harus berisi dua bilangan bulat yang dipisahkan oleh spasi — jarak terbesar yang mungkin ke kode terdekat di antara $k$ kode paling populer, dan banyaknya kode dengan jarak tersebut.

Contoh

Masukan 1

3
00000
00001
12345

Keluaran 1

25 1
24 2
17 270

Masukan 2

3
12345
23456
67890

Keluaran 2

25 1
22 20
12 15270

Catatan

Untuk $k = 1$, jarak terbesar yang mungkin dari kode 00000 adalah 25, hanya dicapai oleh kode 55555.

Untuk $k = 2$, jarak terbesar yang mungkin ke kode yang lebih dekat di antara 00000 dan 00001 adalah 24, dicapai oleh dua kode: 55555 dan 55556. Kode pertama berjarak 24 dari 00001, dan kode kedua berjarak 24 dari 00000.

Untuk $k = 3$, jarak terbesar yang mungkin ke kode terdekat di antara kode 00000, 00001, dan 12345 adalah 17, dicapai oleh 270 kode berbeda, misalnya 55570 dan 55580. Kode pertama berjarak 17 dari 12345, dan kode kedua berjarak 17 dari 00000.