#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  if (a < b) swap(a, b);
  int t;
  while (b) t = a % b, a = b, b = t;
  return a;
}
const int M = 998244353LL;
class Solution {
 public:
  Solution(const string& s) : _n(s.size()), _s(s) {}
  long long solve() {
    long long r = 0, c = 1;
    for (int i = _n - 1; i >= 0; --i) {
      r += c * (_s[i] - '0');
      c = (10 * c) % M;
    }
    for (int x = 1; x <= 9; ++x) {
      for (int y = x + 1; y <= 9; ++y) {
        r += 2LL * solve(x, y);
      }
    }
    return r % M;
  }

 private:
  const int FOUND = (1 << 20) - 1;
  int solve(int x, int y) {
    if (gcd(x, y) != 1) return 0;
    vector<int> t;
    int b = 0;
    for (int d = 1; x * d <= 9 && y * d <= 9; ++d) {
      int m = (1 << (10 + d * x)) | (1 << (d * y));
      t.push_back(m);
      b |= m;
    }
    int r = 0;
    _w.clear();
    tuple<char, char, char, bool, bool, int> init;
    update(init, 1);
    while (!_q.empty()) {
      const auto& u = _q.front();
      auto it = _w.find(u);
      int w = it->second;
      _w.erase(it);
      int k, cx, cy, ex, ey, f;
      tie(k, cx, cy, ex, ey, f) = u;
      _q.pop();
      if (k == _n) {
        if (cx == 0 && cy == 0 && ex == 0 && ey == 0 && f == FOUND) {
          if ((r += w) >= M) r -= M;
        }
        continue;
      }
      for (int d = 0; d < 10; ++d) {
        int ndx = d * x + cx, ndy = d * y + cy;
        int ncx = ndx / 10, ncy = ndy / 10;
        ndx %= 10;
        ndy %= 10;
        int nf = f == FOUND ? f : (f | (1 << (10 + ndx)) | (1 << ndy));
        if (nf != FOUND) {
          nf &= b;
          for (int ti : t)
            if ((ti & nf) == ti) {
              nf = FOUND;
              break;
            }
        }
        int nd = _s[_n - 1 - k] - '0';
        bool nex = (ndx == nd) ? ex : (ndx > nd);
        bool ney = (ndy == nd) ? ey : (ndy > nd);
        update(tuple<char, char, char, bool, bool, int>(k + 1, ncx, ncy, nex,
                                                        ney, nf),
               w);
      }
    }
    return r;
  }
  void update(const tuple<char, char, char, bool, bool, int>& s, int a) {
    auto it = _w.find(s);
    if (it == _w.end()) {
      _q.push(s);
      _w[s] = a;
    } else {
      if ((it->second += a) >= M) it->second -= M;
    }
  }

 private:
  int _n;
  const string& _s;
  map<tuple<char, char, char, bool, bool, int>, int> _w;
  queue<tuple<char, char, char, bool, bool, int> > _q;
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  cout << Solution(s).solve() << endl;
  return 0;
}

### Prompt

Create a solution in Cpp for 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;
int gcd(int a, int b) {
  if (a < b) swap(a, b);
  int t;
  while (b) t = a % b, a = b, b = t;
  return a;
}
const int M = 998244353LL;
class Solution {
 public:
  Solution(const string& s) : _n(s.size()), _s(s) {}
  long long solve() {
    long long r = 0, c = 1;
    for (int i = _n - 1; i >= 0; --i) {
      r += c * (_s[i] - '0');
      c = (10 * c) % M;
    }
    for (int x = 1; x <= 9; ++x) {
      for (int y = x + 1; y <= 9; ++y) {
        r += 2LL * solve(x, y);
      }
    }
    return r % M;
  }

 private:
  const int FOUND = (1 << 20) - 1;
  int solve(int x, int y) {
    if (gcd(x, y) != 1) return 0;
    vector<int> t;
    int b = 0;
    for (int d = 1; x * d <= 9 && y * d <= 9; ++d) {
      int m = (1 << (10 + d * x)) | (1 << (d * y));
      t.push_back(m);
      b |= m;
    }
    int r = 0;
    _w.clear();
    tuple<char, char, char, bool, bool, int> init;
    update(init, 1);
    while (!_q.empty()) {
      const auto& u = _q.front();
      auto it = _w.find(u);
      int w = it->second;
      _w.erase(it);
      int k, cx, cy, ex, ey, f;
      tie(k, cx, cy, ex, ey, f) = u;
      _q.pop();
      if (k == _n) {
        if (cx == 0 && cy == 0 && ex == 0 && ey == 0 && f == FOUND) {
          if ((r += w) >= M) r -= M;
        }
        continue;
      }
      for (int d = 0; d < 10; ++d) {
        int ndx = d * x + cx, ndy = d * y + cy;
        int ncx = ndx / 10, ncy = ndy / 10;
        ndx %= 10;
        ndy %= 10;
        int nf = f == FOUND ? f : (f | (1 << (10 + ndx)) | (1 << ndy));
        if (nf != FOUND) {
          nf &= b;
          for (int ti : t)
            if ((ti & nf) == ti) {
              nf = FOUND;
              break;
            }
        }
        int nd = _s[_n - 1 - k] - '0';
        bool nex = (ndx == nd) ? ex : (ndx > nd);
        bool ney = (ndy == nd) ? ey : (ndy > nd);
        update(tuple<char, char, char, bool, bool, int>(k + 1, ncx, ncy, nex,
                                                        ney, nf),
               w);
      }
    }
    return r;
  }
  void update(const tuple<char, char, char, bool, bool, int>& s, int a) {
    auto it = _w.find(s);
    if (it == _w.end()) {
      _q.push(s);
      _w[s] = a;
    } else {
      if ((it->second += a) >= M) it->second -= M;
    }
  }

 private:
  int _n;
  const string& _s;
  map<tuple<char, char, char, bool, bool, int>, int> _w;
  queue<tuple<char, char, char, bool, bool, int> > _q;
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  cout << Solution(s).solve() << endl;
  return 0;
}

```