Problem: A dial lock is a kind of lock which has some dials with printed numbers. It has a special sequence of numbers, namely an unlocking sequence, to be opened.

You are working at a manufacturer of dial locks. Your job is to verify that every manufactured lock is unlocked by its unlocking sequence. In other words, you have to rotate many dials of many many locks.

It’s a very hard and boring task. You want to reduce time to open the locks. It’s a good idea to rotate multiple dials at one time. It is, however, a difficult problem to find steps to open a given lock with the fewest rotations. So you decided to write a program to find such steps for given initial and unlocking sequences.

Your company’s dial locks are composed of vertically stacked k (1 ≤ k ≤ 10) cylindrical dials. Every dial has 10 numbers, from 0 to 9, along the side of the cylindrical shape from the left to the right in sequence. The neighbor on the right of 9 is 0.

A dial points one number at a certain position. If you rotate a dial to the left by i digits, the dial newly points the i-th right number. In contrast, if you rotate a dial to the right by i digits, it points the i-th left number. For example, if you rotate a dial pointing 8 to the left by 3 digits, the dial newly points 1.

You can rotate more than one adjacent dial at one time. For example, consider a lock with 5 dials. You can rotate just the 2nd dial. You can rotate the 3rd, 4th and 5th dials at the same time. But you cannot rotate the 1st and 3rd dials at one time without rotating the 2nd dial. When you rotate multiple dials, you have to rotate them to the same direction by the same digits.

Your program is to calculate the fewest number of rotations to unlock, for given initial and unlocking sequences. Rotating one or more adjacent dials to the same direction by the same digits is counted as one rotation.



Input

The input consists of multiple datasets. Each datset consists of two lines. The first line contains an integer k. The second lines contain two strings, separated by a space, which indicate the initial and unlocking sequences.

The last dataset is followed by a line containing one zero. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the minimum number of rotations in one line.

Example

Input

4
1357 4680
6
777777 003330
0


Output

1
2

Solution (in CPP):

Solution:
#include<stdio.h>
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <functional>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <string>
#include <assert.h>
#include <stdio.h>
#include <queue>
#include<iomanip>
#include<bitset>
#include<stack>
using namespace std;

const long long int mod = 1000000007;

struct Mod {
	int num;
	Mod() : num(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) { ; }
	Mod(int n) : num((n % mod + mod) % mod) { ; }
	operator int() { return num; }
};

Mod operator+(Mod a, Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(long long int a, Mod b) { return Mod(a) + b; }
Mod operator-(Mod a, Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(long long int a, Mod b) { return Mod(a) - b; }
Mod operator*(Mod a, Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(long long int a, Mod b) { return Mod(a)*b; }
Mod operator+=(Mod &a, Mod b) { return a = a + b; }
Mod operator+=(long long int &a, Mod b) { return a = a + b; }
Mod operator-=(Mod &a, Mod b) { return a = a - b; }
Mod operator-=(long long int &a, Mod b) { return a = a - b; }
Mod operator*=(Mod &a, Mod b) { return a = a * b; }
Mod operator*=(long long int &a, Mod b) { return a = a * b; }
Mod operator^(Mod a, long long int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod inv(Mod a) { return a ^ (mod - 2); }
Mod operator/(Mod a, Mod b) {
	assert(b != 0);
	return a * inv(b);
}
Mod operator/(long long int a, Mod b) {
	assert(b != 0);
	return Mod(a) * inv(b);
}

#define MAX_N 1024000

Mod fact[MAX_N], factinv[MAX_N];
void init() {
	fact[0] = Mod(1); factinv[0] = 1;
	for (int i = 0; i < MAX_N - 1; ++i) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
}
Mod comb(int a, int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}


#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()



/* 幾何の基本 */

#include <complex>

typedef long double ld;
typedef complex<ld> Point;

const ld eps = 1e-9, pi = acos(-1.0);

namespace std {
  bool operator<(const Point &lhs, const Point &rhs) {
    if (lhs.real() < rhs.real() - eps) return true;
    if (lhs.real() > rhs.real() + eps) return false;
    return lhs.imag() < rhs.imag();
  }
}

// 点の入力
Point input_point() {
  ld x, y;
  cin >> x >> y;
  return Point(x, y);
}

// 誤差つき等号判定
bool eq(ld a, ld b) {
  return (abs(a - b) < eps);
}

// 内積
ld dot(Point a, Point b) {
  return real(conj(a) * b);
}

// 外積
ld cross(Point a, Point b) {
  return imag(conj(a) * b);
}

// 直線の定義
class Line {
public:
  Point a, b;
  Line () : a(Point(0, 0)), b(Point(0, 0)) {}
  Line (Point a, Point b) : a(a), b(b) {}
};

// 円の定義
class Circle {
public:
  Point p;
  ld r;
  Circle () : p(Point(0, 0)), r(0) {}
  Circle (Point p, ld r) : p(p), r(r) {}
};

// CCW
int ccw (Point a, Point b, Point c) {
  b -= a; c -= a;
  if (cross(b, c) > eps) return 1;   // a,b,cが反時計周りの順に並ぶ
  if (cross(b, c) < -eps) return -1; // a,b,cが時計周りの順に並ぶ
  if (dot(b, c) < 0) return 2;       // c,a,bの順に直線に並ぶ
  if (norm(b) < norm(c)) return -2;  // a,b,cの順に直線に並ぶ
  return 0;                          // a,c,bの順に直線に並ぶ
}


/* 交差判定 */

// 直線と直線の交差判定
bool isis_ll (Line l, Line m) {
  return !eq(cross(l.b - l.a, m.b - m.a), 0);
}

// 直線と線分の交差判定
bool isis_ls (Line l, Line s) {
  return isis_ll(l, s) &&
    (cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < eps);
}

// 線分と線分の交差判定
bool isis_ss(Line s, Line t) {
  return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
    ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

// 点の直線上判定
bool isis_lp (Line l, Point p) {
  return (abs(cross(l.b - p, l.a - p)) < eps);
}

// 点の線分上判定
bool isis_sp (Line s, Point p) {
  return (abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps);
}

// 垂線の足
Point proj (Line l, Point p) {
  ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
  return l.a + t * (l.a - l.b);
}

// 直線と直線の交点
Point is_ll (Line s, Line t) {
  Point sv = s.b - s.a, tv = t.b - t.a;
  assert(cross(sv, tv) != 0);
  return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}

// 直線と点の距離
ld dist_lp (Line l, Point p) {
  return abs(p - proj(l, p));
}

// 直線と直線の距離
ld dist_ll (Line l, Line m) {
  return isis_ll(l, m) ? 0 : dist_lp(l, m.a);
}

// 直線と線分の距離
ld dist_ls (Line l, Line s) {
  return isis_ls(l, s) ? 0 : min(dist_lp(l, s.a), dist_lp(l, s.b));
}

// 線分と点の距離
ld dist_sp (Line s, Point p) {
  Point r = proj(s, p);
  return isis_sp(s, r) ? abs(r - p) : min(abs(s.a - p), abs(s.b - p));
}

// 線分と線分の距離
ld dist_ss (Line s, Line t) {
  if (isis_ss(s, t)) return 0;
  return min({dist_sp(s, t.a), dist_sp(s, t.b), dist_sp(t, s.a), dist_sp(t, s.b)});
}


/* 円 */

// 円と円の交点
vector<Point> is_cc (Circle c1, Circle c2){
  vector<Point> res;
  ld d = abs(c1.p - c2.p);
  ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
  ld dfr = c1.r * c1.r - rc * rc;
  if (abs(dfr) < eps) dfr = 0.0;
  else if (dfr < 0.0) return res; // no intersection
  ld rs = sqrt(dfr);
  Point diff = (c2.p - c1.p) / d;
  res.push_back(c1.p + diff * Point(rc, rs));
  if (dfr != 0.0) res.push_back(c1.p + diff * Point(rc, -rs));
  return res;
}

// 円と直線の交点
vector<Point> is_lc (Circle c, Line l){
  vector<Point> res;
  ld d = dist_lp(l, c.p);
  if (d < c.r + eps){
    ld len = (d > c.r) ? 0.0 : sqrt(c.r * c.r - d * d); //safety;
    Point nor = (l.a - l.b) / abs(l.a - l.b);
    res.push_back(proj(l, c.p) + len * nor);
    res.push_back(proj(l, c.p) - len * nor);
  }
  return res;
}

// 円と線分の距離
vector<Point> is_sc(Circle c, Line l){
  vector<Point> v = is_lc(c, l), res;
  for (Point p : v)
    if (isis_sp(l, p)) res.push_back(p);
  return res;
}

// 円と点の接線
vector<Line> tangent_cp(Circle c, Point p) {
  vector<Line> ret;
  Point v = c.p - p;
  ld d = abs(v);
  ld l = sqrt(norm(v) - c.r * c.r);
  if (isnan(l)) { return ret; }
  Point v1 = v * Point(l / d,  c.r / d);
  Point v2 = v * Point(l / d, -c.r / d);
  ret.push_back(Line(p, p + v1));
  if (l < eps) return ret;
  ret.push_back(Line(p, p + v2));
  return ret;
}

// 円と円の接線
vector<Line> tangent_cc(Circle c1, Circle c2) {
  vector<Line> ret;
  if (abs(c1.p - c2.p) - (c1.r + c2.r) > -eps) {
    Point center = (c1.p * c2.r + c2.p * c1.r) / (c1.r + c2.r);
    ret = tangent_cp(c1, center);
  }
  if (abs(c1.r - c2.r) > eps) {
    Point out = (-c1.p * c2.r + c2.p * c1.r) / (c1.r - c2.r);
    vector<Line> nret = tangent_cp(c1, out);
    ret.insert(ret.end(), ALL(nret));
  }
  else {
    Point v = c2.p - c1.p;
    v /= abs(v);
    Point q1 = c1.p + v * Point(0,  1) * c1.r;
    Point q2 = c1.p + v * Point(0, -1) * c1.r;
    ret.push_back(Line(q1, q1 + v));
    ret.push_back(Line(q2, q2 + v));
  }
  return ret;
}


/* 多角形 */

typedef vector<Point> Polygon;

// 面積
ld area(const Polygon &p) {
  ld res = 0;
  int n = p.size();
  REP(j,n) res += cross(p[j], p[(j+1)%n]);
  return res / 2;
}

// 多角形の回転方向
bool is_counter_clockwise (const Polygon &poly) {
  ld angle = 0;
  int n = poly.size();
  REP(i,n) {
    Point a = poly[i], b = poly[(i+1)%n], c = poly[(i+2)%n];
    angle += arg((c - b) / (b - a));
  }
  return angle > eps;
}

// 円の内外判定
// -1 => out
//  0 => on
//  1 => in
int is_in_polygon (const Polygon &poly, Point p) {
  ld angle = 0;
  int n = poly.size();
  REP(i,n) {
    Point a = poly[i], b = poly[(i+1)%n];
    if (isis_sp(Line(a, b), p)) return 1;
    angle += arg((b - p) / (a - p));
  }
  return eq(angle, 0) ? 0 : 2;
}

// 凸包
Polygon convex_hull(vector<Point> ps) {
  int n = ps.size();
  int k = 0;
  sort(ps.begin(), ps.end());
  Polygon ch(2 * n);
  for (int i = 0; i < n; ch[k++] = ps[i++])
    while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
  for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--])
    while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
  ch.resize(k - 1);
  return ch;
}

// 凸カット
Polygon convex_cut(const Polygon &ps, Line l) {
  int n = ps.size();
  Polygon Q;
  REP(i,n) {
    Point A = ps[i], B = ps[(i+1)%n];
    Line m = Line(A, B);
    if (ccw(l.a, l.b, A) != -1) Q.push_back(A);
    if (ccw(l.a, l.b, A) * ccw(l.a, l.b, B) < 0 && isis_ll(l, m))
      Q.push_back(is_ll(l, m));
  }
  return Q;
}


/* アレンジメント */
void add_point(vector<Point> &ps, Point p) {
  for (Point q : ps) if (abs(q - p) < eps) return;
  ps.push_back(p);
}

typedef int Weight;

struct Edge { int from, to; Weight weight; };

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &g, int from, int to, Weight weight) {
  g[from].push_back(Edge{from, to, weight});
}

Graph segment_arrangement(const vector<Line> &s, const vector<Point> &p) {
  int n = p.size(), m = s.size();
  Graph g(n);
  REP(i,m) {
    vector<pair<ld,int>> vec;
    REP(j,n) if (isis_sp(s[i], p[j]))
      vec.emplace_back(abs(s[i].a - p[j]), j);
    sort(ALL(vec));
    REP(j,vec.size()-1) {
      int from = vec[j].second, to = vec[j+1].second;
      add_edge(g, from, to, abs(p[from] - p[to]));
    }
  }
  return g;
}

Graph circle_arrangement(const vector<Circle> &c, const vector<Point> &p) {
  int n = p.size(), m = c.size();
  Graph g(n);
  REP(i,m) {
    vector<pair<ld,int>> vec;
    REP(j,n) if (abs(abs(c[i].p - p[j]) - c[i].r) < eps)
      vec.emplace_back(arg(c[i].p - p[j]), j);
    sort(ALL(vec));
    REP(j,vec.size()-1) {
      int from = vec[j].second, to = vec[j+1].second;
      ld angle = vec[j+1].first - vec[j].first;
      add_edge(g, from, to, angle * c[i].r);
    }
    if (vec.size() >= 2) {
      int from = vec.back().second, to = vec.front().first;
      ld angle = vec.front().first - vec.back().first;
      add_edge(g, from, to, angle * c[i].r);
    }
  }
  return g;
}


/* 双対グラフ */

// 線分集合は既にアレンジメントされていなければならない．
// 内側の円は時計回りで，外側の円は反時計回りで得られる．
// 変数 polygon は，vector<int> で表される多角形の集合であり，
// vector<int> で表される 多角形のi番目は，その頂点の頂点集合pにおける番号である．
vector<vector<int>> polygon;
vector<int> seg2p[1024][1024];

Graph dual_graph(const vector<Line> &s, const vector<Point> &p) {
  int N = p.size();
  polygon.clear();
  REP(i,1024) REP(j,1024) seg2p[i][j].clear();
  vector<vector<tuple<ld,int,bool>>> tup(N);
  REP(i,s.size()) {
    int a = -1, b = -1;
    REP(j,N) if (abs(s[i].a - p[j]) < eps) a = j;
    REP(j,N) if (abs(s[i].b - p[j]) < eps) b = j;
    assert(a >= 0 && b >= 0);
    tup[a].emplace_back(arg(s[i].b - s[i].a), b, false);
    tup[b].emplace_back(arg(s[i].a - s[i].b), a, false);
  }
  REP(i,N) sort(ALL(tup[i]));
  REP(i,N) {
    REP(j,tup[i].size()) {
      ld angle; int pos = j, from = i, to; bool flag;
      tie(angle, to, flag) = tup[i][j];
      if (flag) continue;
      vector<int> ps;
      while (!flag) {
        ps.push_back(from);
        get<2>(tup[from][pos]) = true;
        seg2p[from][to].push_back(polygon.size());
        seg2p[to][from].push_back(polygon.size());
        angle += pi + eps;
        if (angle > pi) angle -= 2 * pi;
        auto it = lower_bound(ALL(tup[to]), make_tuple(angle, 0, false));
        if (it == tup[to].end()) it = tup[to].begin();
        from = to; tie(angle, to, flag) = *it;
        pos = it - tup[from].begin();
      }
      polygon.push_back(ps);
    }
  }
  Graph g(polygon.size());
  REP(i,N) REP(j,i) {
    if (seg2p[i][j].size() == 2) {
      int from = seg2p[i][j][0], to = seg2p[i][j][1];
      g[from].push_back(Edge{from, to});
      g[to].push_back(Edge{to, from});
    }
  }
  return g;
}


/* ビジュアライザ */
const ld zoom = 25;
const ld centerX = 6;
const ld centerY = 5;

void change_color(int r, int g, int b) {
  fprintf(stderr, "c.strokeStyle = 'rgb(%d, %d, %d)';\n", r, g, b);
}

int cordx(Point p) { return 400 + zoom * (p.real() - centerX); }
int cordy(Point p) { return 400 - zoom * (p.imag() - centerY); }

#define cord(p) cordx(p),cordy(p)

void draw_point(Point p) {
  fprintf(stderr, "circle(%d, %d, %d)\n", cord(p), 2);
}

void draw_segment(Line l) {
  fprintf(stderr, "line(%d, %d, %d, %d)\n", cord(l.a), cord(l.b));
}

void draw_line(Line l) {
  Point v = l.b - l.a;
  Line m(l.a - v * Point(1e4, 0), l.b + v * Point(1e4, 0));
  fprintf(stderr, "line(%d, %d, %d, %d)\n", cord(m.a), cord(m.b));
}

void draw_polygon(const Polygon &p) {
  int n = p.size();
  REP(i,n) draw_segment(Line(p[i], p[(i+1)%n]));
}

void draw_circle(Circle c) {
  fprintf(stderr, "circle(%d, %d, %d)\n", cord(c.p), (int)(zoom * c.r));
}

class Compare {
public:
	bool operator()(const pair<int, double>&l, const pair<int, double>&r) {
		return l.second > r.second;
	}
};


int getans(vector<int>Sa) {
	if (Sa.size() == 1) {
		if (Sa[0] == 0)return 0;
		else return 1;
	}
	else {
		if (Sa[0] == 0) {
			int ans = 10;
			for (int i = 0; i < Sa.size(); ++i) {
				vector<int>nSa(Sa); 
				for (int j = 1; j <i+1; ++j) {
					nSa[j] -= Sa[0];
					nSa[j] += 10;
					nSa[j] %= 10;

					
				}
				ans = min(ans, getans(vector<int>(nSa.begin() + 1, nSa.end())));
			}
			return ans;
		}
		else {
			int ans =10;
			for (int i = 0; i < Sa.size(); ++i) {
				vector<int>nSa(Sa);
				for (int j = 1; j <i+1; ++j) {
					nSa[j] -= Sa[0];
					nSa[j] += 10;
					nSa[j] %= 10;
				}

				ans = min(ans, 1 + getans(vector<int>(nSa.begin() + 1, nSa.end())));
			}
			return ans;
		}
	}
}

int main() {
	/*int a, b;
	cin >> a >> b;
	vector<Point> totaps;
	vector<Point> tuteps;
	for (int i = 0; i < a; ++i) {
		double x;
		double y;
		cin >> x >> y;
		totaps.push_back(Point(x, y));
	}
	for (int i = 0; i < b; ++i) {
		double x;
		double y;
		cin >> x >> y;
		tuteps.push_back(Point(x, y));
	}
	double ans1 = 0;
	{
		Line totaload(totaps[0], totaps[1]);
		vector<vector<pair<int,double>>>Nodes(b);
		for (int i = 0; i < b; ++i) {
			for (int j = 0; j < b; ++j) {
				if (i != j) {
					if (!isis_ss(totaload, Line(tuteps[i], tuteps[j]))) {
						double dis = abs(tuteps[i] - tuteps[j]);
						Nodes[i].push_back(make_pair(j, dis));
					}
				}
			}
		}
		vector<double>times(b, 999999999999);
		times[0] = 0;
		priority_queue<pair<int, double>,vector<pair<int, double>>,Compare>qu;
		qu.push(make_pair(0, 0));
		while (!qu.empty()) {
			pair<int, double> atop = qu.top();
			qu.pop();
			for (int i = 0; i < Nodes[atop.first].size(); ++i) {
				if (times[Nodes[atop.first][i].first]>atop.second + Nodes[atop.first][i].second) {
					qu.push(make_pair(Nodes[atop.first][i].first,atop.second + Nodes[atop.first][i].second));
					times[Nodes[atop.first][i].first] = atop.second + Nodes[atop.first][i].second;
				}
			}
		}
		ans1= abs(totaload.a-totaload.b);
		ans1 += times[1];
	}
	double ans2 = 0;
	{
		Line tuteload(tuteps[0], tuteps[1]);
		vector<vector<pair<int, double>>>Nodes(a);
		for (int i = 0; i < a; ++i) {
			for (int j = 0; j < a; ++j) {
				if (i != j) {
					if (!isis_ss(tuteload, Line(totaps[i], totaps[j]))) {
						double dis=abs(totaps[i] - totaps[j]);
						Nodes[i].push_back(make_pair(j, dis));
					}
				}
			}
		}
		vector<double>times(a, 999999999999);
		times[0] = 0;
		priority_queue<pair<int, double>, vector<pair<int, double>>, Compare>qu;
		qu.push(make_pair(0, 0));
		while (!qu.empty()) {
			pair<int, double> atop = qu.top();
			qu.pop();
			for (int i = 0; i < Nodes[atop.first].size(); ++i) {
				if (times[Nodes[atop.first][i].first]>atop.second + Nodes[atop.first][i].second) {
					qu.push(make_pair(Nodes[atop.first][i].first, atop.second + Nodes[atop.first][i].second));
					times[Nodes[atop.first][i].first] = atop.second + Nodes[atop.first][i].second;
				}
			}
		}
		ans2 = abs(tuteload.a - tuteload.b);
		ans2 += times[1];
	}
	double ans = min(ans1, ans2);
	if (ans > 999999999990) {
		cout << -1 << endl;
	}else{
		cout <<fixed<<setprecision(20)<< ans << endl;
	}
	return 0;*/	
	while (1) {
		int a;
		cin >> a;
		if (a) {
			string l, r;
			cin >> l >> r;
			vector<int>Sa;
			for (int i = 0; i < a; ++i) {
				Sa.push_back((10+l[i] - r[i])%10);
			}
			int ans = getans(Sa);
			cout << ans << endl;
			
		}
		else {
			return 0;
		}
	}
	
}