問題
ミズゴロウのゴロウくんは, DCPC ( Dice Counting Programming Contest ) に出場するために, N 桁のカウンターで数をかぞえる特訓を毎日している.彼が練習しているカウンターには, 次の2つの機能があり, ゴロウくんは, 1 秒間に 1 度だけどちらかの機能を使うことができる.
- 表示されている数に 1 を加算する. ただし, 表示されている数がカウンターで表せる数の最大値だった場合, 0 に戻る. たとえば N = 3 のとき, 101 は 102 , 999 は 000 に変わる.
- カウンターの先頭の桁と同じ値の全ての桁に 1 を加算する. ただし, 先頭の数が 9 だった場合, それらの数はすべて 0 になる. たとえば, N = 4 のとき, 1131 は 2232 , 9982 は 0082 に変わる.
ゴロウくんは, M 個の数の組 ( Ai , Bi )について, このカウンターで, Ai から初めて Bi を作るのに最短で何秒かかるのかが気になった. 入力として N, M の値と M 個の数の組 ( Ai, Bi ) が与えられるとき, Ai から初めて Bi を作るのに必要な秒数の最小値を求めよ.
入力
入力は M + 1 行からなる.
1 行目には 2 つの整数 N, M ( 1 ≦ N ≦ 6 , 1 ≦ M ≦ 1000 ) が空白を区切りとして書かれている.
1 + i 行目には, 2 つの整数 Ai, Bi (0 ≦ Ai , Bi ＜ 10N)が空白を区切りとして書かれている.
ここで, i ≠ j であれば, Ai ≠ Aj または Bi ≠ Bj が保証されている.
出力
i ( 1 ≦ i ≦ M ) 行目に, Ai から初めて Bi を作るのに必要な秒数の最小値を求めよ.
入出力例
入力例 1
3 5 000 001 123 224 000 999 999 000 000 998
出力例 1
1 2 9 1 19