#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return a == 0 ? b : gcd(b % a, a); }
struct op {
  long long a;
  long long b;
  long long c;
  long long d;
  long long e;
  op(long long aa, long long bb, long long cc, long long dd, long long ee) {
    a = aa, b = bb, c = cc, d = dd, e = ee;
  }
  op() {}
  bool cnts() const {
    if (a == 0 && b == 0 && c == 0) return d & e;
    return false;
  }
  bool operator<(op b) const {
    if (this->a == b.a) {
      if (this->b == b.b) {
        if (this->c == b.c) {
          if (this->d == b.d) {
            return this->e < b.e;
          }
          return this->d < b.d;
        }
        return this->c < b.c;
      }
      return this->b < b.b;
    }
    return this->a < b.a;
  }
};
string s;
long long yk;
long long solve(long long x, long long y) {
  map<op, long long> DP[102];
  long long Ans = 0, aa, bb, cc, dd, ee;
  DP[0][op(0, 0, 0, 0, 0)] = 1;
  for (long long i = 0; i < 101; i++) {
    for (auto& it : DP[i]) {
      for (long long k = 0; k <= 9; k++) {
        aa = it.first.a + k * x, bb = it.first.b + k * y, cc = it.first.c,
        dd = it.first.d, ee = it.first.e;
        if (cc) {
          if (aa % 10 < s[i] - '0') {
            cc = 0;
          }
        } else {
          if (aa % 10 > s[i] - '0') {
            cc = 1;
          }
        }
        if (dd & ee) {
        }
        if (aa % 10 % x == 0 && aa % 10 > 0 && (aa % 10 / x) <= yk) {
          dd |= 1 << (aa % 10 / x);
        }
        if (bb % 10 % y == 0 && bb % 10 > 0 && (bb % 10 / y) <= yk) {
          ee |= 1 << (bb % 10 / y);
        }
        if (dd & ee) {
          dd = 1, ee = 1;
        }
        op ops = op(aa / 10, bb / 10, cc, dd, ee);
        DP[i + 1][ops] += it.second;
        DP[i + 1][ops] %= 998244353;
      }
    }
  }
  for (auto& it : DP[101]) {
    if (it.first.cnts()) {
      Ans += it.second;
    }
  }
  return Ans;
}
signed main() {
  cin >> s;
  reverse(s.begin(), s.end());
  for (long long i = 1; i <= 101; i++) {
    s += '0';
  }
  long long Sum, Ans = 0;
  for (long long i = 1; i <= 9; i++) {
    for (long long j = 1; j < i; j++) {
      if (gcd(i, j) == 1) {
        yk = 9 / i;
        Sum = solve(i, j);
        Ans += Sum * 2;
        Ans %= 998244353;
      }
    }
  }
  yk = 9;
  Ans += solve(1, 1);
  Ans %= 998244353;
  Ans %= 998244353;
  cout << Ans << '\n';
  return 0;
}

### Prompt

In Cpp, your task is to solve the following problem:

Let's call a fraction x/y good if there exists at least one another fraction (x')/(y') such that x/y = (x')/(y'), 1 ≤ x', y' ≤ 9, the digit denoting x' is contained in the decimal representation of x, and the digit denoting y' is contained in the decimal representation of y. For example, 26/13 is a good fraction, because 26/13 = 2/1.

You are given an integer number n. Please calculate the number of good fractions x/y such that 1 ≤ x ≤ n and 1 ≤ y ≤ n. The answer may be really large, so print it modulo 998244353.

Input

The only line of the input contains one integer n (1 ≤ n < 10^{100}).

Output

Print the number of good fractions x/y such that 1 ≤ x ≤ n and 1 ≤ y ≤ n. The answer may be really large, so print it modulo 998244353.

Examples

Input


42


Output


150


Input


3141592653589793238462643383279


Output


459925407

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return a == 0 ? b : gcd(b % a, a); }
struct op {
  long long a;
  long long b;
  long long c;
  long long d;
  long long e;
  op(long long aa, long long bb, long long cc, long long dd, long long ee) {
    a = aa, b = bb, c = cc, d = dd, e = ee;
  }
  op() {}
  bool cnts() const {
    if (a == 0 && b == 0 && c == 0) return d & e;
    return false;
  }
  bool operator<(op b) const {
    if (this->a == b.a) {
      if (this->b == b.b) {
        if (this->c == b.c) {
          if (this->d == b.d) {
            return this->e < b.e;
          }
          return this->d < b.d;
        }
        return this->c < b.c;
      }
      return this->b < b.b;
    }
    return this->a < b.a;
  }
};
string s;
long long yk;
long long solve(long long x, long long y) {
  map<op, long long> DP[102];
  long long Ans = 0, aa, bb, cc, dd, ee;
  DP[0][op(0, 0, 0, 0, 0)] = 1;
  for (long long i = 0; i < 101; i++) {
    for (auto& it : DP[i]) {
      for (long long k = 0; k <= 9; k++) {
        aa = it.first.a + k * x, bb = it.first.b + k * y, cc = it.first.c,
        dd = it.first.d, ee = it.first.e;
        if (cc) {
          if (aa % 10 < s[i] - '0') {
            cc = 0;
          }
        } else {
          if (aa % 10 > s[i] - '0') {
            cc = 1;
          }
        }
        if (dd & ee) {
        }
        if (aa % 10 % x == 0 && aa % 10 > 0 && (aa % 10 / x) <= yk) {
          dd |= 1 << (aa % 10 / x);
        }
        if (bb % 10 % y == 0 && bb % 10 > 0 && (bb % 10 / y) <= yk) {
          ee |= 1 << (bb % 10 / y);
        }
        if (dd & ee) {
          dd = 1, ee = 1;
        }
        op ops = op(aa / 10, bb / 10, cc, dd, ee);
        DP[i + 1][ops] += it.second;
        DP[i + 1][ops] %= 998244353;
      }
    }
  }
  for (auto& it : DP[101]) {
    if (it.first.cnts()) {
      Ans += it.second;
    }
  }
  return Ans;
}
signed main() {
  cin >> s;
  reverse(s.begin(), s.end());
  for (long long i = 1; i <= 101; i++) {
    s += '0';
  }
  long long Sum, Ans = 0;
  for (long long i = 1; i <= 9; i++) {
    for (long long j = 1; j < i; j++) {
      if (gcd(i, j) == 1) {
        yk = 9 / i;
        Sum = solve(i, j);
        Ans += Sum * 2;
        Ans %= 998244353;
      }
    }
  }
  yk = 9;
  Ans += solve(1, 1);
  Ans %= 998244353;
  Ans %= 998244353;
  cout << Ans << '\n';
  return 0;
}

```