005 - カウンター (Counter)

問題

ミズゴロウのゴロウくんは, 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 ＜ 10^N)が空白を区切りとして書かれている.
ここで, 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