#include <bits/stdc++.h>
using namespace std;
char buf[1 << 21], *p1 = buf, *p2 = buf;
template <class T>
void read(T &x) {
  x = 0;
  int c = getchar();
  int flag = 0;
  while (c < '0' || c > '9') flag |= (c == '-'), c = getchar();
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
template <class T>
T _max(T a, T b) {
  return b < a ? a : b;
}
template <class T>
T _min(T a, T b) {
  return a < b ? a : b;
}
template <class T>
bool checkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
bool checkmin(T &a, T b) {
  return b < a ? a = b, 1 : 0;
}
const int mod = 998244353;
char s[105];
int n;
int a[105];
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
void add(int &a, int b) {
  a += b;
  (a >= mod) && (a -= mod);
}
int f[10][10][2][16][16];
int g[10][10][2][16][16];
void init() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
}
int run(int P, int Q) {
  int lim = 9 / Q;
  int full = (1 << lim) - 1;
  memset(f, 0, sizeof f);
  memset(g, 0, sizeof g);
  f[0][0][0][0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int c1 = 0; c1 < 10; ++c1) {
      for (int c2 = 0; c2 < 10; ++c2) {
        for (int gt = 0; gt < 2; ++gt) {
          for (int m1 = 0; m1 <= full; ++m1) {
            for (int m2 = 0; m2 <= full; ++m2) {
              int num = f[c1][c2][gt][m1][m2];
              if (num == 0) continue;
              for (int b = 0; b <= 9; ++b) {
                int b1 = (b * P + c1) % 10, b2 = (b * Q + c2) % 10;
                int _c1 = (b * P + c1) / 10, _c2 = (b * Q + c2) / 10;
                int _m1 = m1, _m2 = m2;
                if (b1 && b1 % P == 0 && b1 / P <= lim)
                  _m1 |= (1 << ((b1 / P) - 1));
                if (b2 && b2 % Q == 0 && b2 / Q <= lim)
                  _m2 |= (1 << ((b2 / Q) - 1));
                int _gt;
                if (b > a[i])
                  _gt = 1;
                else if (b < a[i])
                  _gt = 0;
                else
                  _gt = gt;
                add(g[_c1][_c2][_gt][_m1][_m2], num);
              }
            }
          }
        }
      }
    }
    for (int c1 = 0; c1 < 10; ++c1) {
      for (int c2 = 0; c2 < 10; ++c2) {
        for (int gt = 0; gt < 2; ++gt) {
          for (int m1 = 0; m1 <= full; ++m1) {
            for (int m2 = 0; m2 <= full; ++m2) {
              f[c1][c2][gt][m1][m2] = g[c1][c2][gt][m1][m2];
              g[c1][c2][gt][m1][m2] = 0;
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i <= full; ++i)
    for (int j = 0; j <= full; ++j)
      if (i & j) {
        add(ans, f[0][0][0][i][j]);
      }
  return ans;
}
void solve() {
  int ans = 0;
  for (int p = 1; p <= 9; ++p)
    for (int q = p + 1; q <= 9; ++q)
      if (gcd(p, q) == 1) {
        int t = 0;
        for (int i = 1; i <= n; ++i) {
          t = t * 10 + s[i] - '0';
          a[i] = t / q;
          t %= q;
        }
        reverse(a + 1, a + n + 1);
        add(ans, run(p, q));
      }
  add(ans, ans);
  int z = 0;
  for (int i = 1; i <= n; ++i) z = (10LL * z + s[i] - 48) % mod;
  add(ans, z);
  printf("%d\n", ans);
}
int main() {
  init();
  solve();
  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;
char buf[1 << 21], *p1 = buf, *p2 = buf;
template <class T>
void read(T &x) {
  x = 0;
  int c = getchar();
  int flag = 0;
  while (c < '0' || c > '9') flag |= (c == '-'), c = getchar();
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
template <class T>
T _max(T a, T b) {
  return b < a ? a : b;
}
template <class T>
T _min(T a, T b) {
  return a < b ? a : b;
}
template <class T>
bool checkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
bool checkmin(T &a, T b) {
  return b < a ? a = b, 1 : 0;
}
const int mod = 998244353;
char s[105];
int n;
int a[105];
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
void add(int &a, int b) {
  a += b;
  (a >= mod) && (a -= mod);
}
int f[10][10][2][16][16];
int g[10][10][2][16][16];
void init() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
}
int run(int P, int Q) {
  int lim = 9 / Q;
  int full = (1 << lim) - 1;
  memset(f, 0, sizeof f);
  memset(g, 0, sizeof g);
  f[0][0][0][0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int c1 = 0; c1 < 10; ++c1) {
      for (int c2 = 0; c2 < 10; ++c2) {
        for (int gt = 0; gt < 2; ++gt) {
          for (int m1 = 0; m1 <= full; ++m1) {
            for (int m2 = 0; m2 <= full; ++m2) {
              int num = f[c1][c2][gt][m1][m2];
              if (num == 0) continue;
              for (int b = 0; b <= 9; ++b) {
                int b1 = (b * P + c1) % 10, b2 = (b * Q + c2) % 10;
                int _c1 = (b * P + c1) / 10, _c2 = (b * Q + c2) / 10;
                int _m1 = m1, _m2 = m2;
                if (b1 && b1 % P == 0 && b1 / P <= lim)
                  _m1 |= (1 << ((b1 / P) - 1));
                if (b2 && b2 % Q == 0 && b2 / Q <= lim)
                  _m2 |= (1 << ((b2 / Q) - 1));
                int _gt;
                if (b > a[i])
                  _gt = 1;
                else if (b < a[i])
                  _gt = 0;
                else
                  _gt = gt;
                add(g[_c1][_c2][_gt][_m1][_m2], num);
              }
            }
          }
        }
      }
    }
    for (int c1 = 0; c1 < 10; ++c1) {
      for (int c2 = 0; c2 < 10; ++c2) {
        for (int gt = 0; gt < 2; ++gt) {
          for (int m1 = 0; m1 <= full; ++m1) {
            for (int m2 = 0; m2 <= full; ++m2) {
              f[c1][c2][gt][m1][m2] = g[c1][c2][gt][m1][m2];
              g[c1][c2][gt][m1][m2] = 0;
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i <= full; ++i)
    for (int j = 0; j <= full; ++j)
      if (i & j) {
        add(ans, f[0][0][0][i][j]);
      }
  return ans;
}
void solve() {
  int ans = 0;
  for (int p = 1; p <= 9; ++p)
    for (int q = p + 1; q <= 9; ++q)
      if (gcd(p, q) == 1) {
        int t = 0;
        for (int i = 1; i <= n; ++i) {
          t = t * 10 + s[i] - '0';
          a[i] = t / q;
          t %= q;
        }
        reverse(a + 1, a + n + 1);
        add(ans, run(p, q));
      }
  add(ans, ans);
  int z = 0;
  for (int i = 1; i <= n; ++i) z = (10LL * z + s[i] - 48) % mod;
  add(ans, z);
  printf("%d\n", ans);
}
int main() {
  init();
  solve();
  return 0;
}

```