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$ 行，每行包含一個由 5 個 0–9 數字組成嘅字串，可以有前導零。呢啲就係按最熱門到最唔熱門排列嘅熱門密碼。所有密碼兩兩唔同。

輸出格式

輸出 $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，有 270 個唔同嘅密碼可以達到，例如 55570 同 55580。第一個離 12345 距離係 17，第二個離 00000 距離係 17。