#include <bits/stdc++.h>
#pragma GCC optimize("O3")
int gcd(int a, int b) {
  if (a % b == 0)
    return b;
  else
    return gcd(b, a % b);
};
long long dp[10][10][(1 << 8)][2][2];
int zbt[10];
int nbt[10];
char str[120];
std::vector<int> ddiv;
std::vector<int> num;
long long calc(int z, int n) {
  memset(zbt, -1, sizeof(zbt));
  memset(nbt, -1, sizeof(nbt));
  memset(dp, 0, sizeof(dp));
  int add = 0;
  for (int i = 1; i * n < 10; i++) {
    zbt[i * z] = i - 1;
    nbt[i * n] = i - 1;
    add = i;
  };
  int shft = add * 2;
  dp[0][0][0][0][0] = 1;
  for (int i = 1; i <= ddiv.size(); i++) {
    for (int k1 = 0; k1 < 10; k1++) {
      for (int k2 = 0; k2 < 10; k2++) {
        for (int m = 0; m < (1 << (shft)); m++) {
          dp[k1][k2][m][i % 2][0] = 0;
          dp[k1][k2][m][i % 2][1] = 0;
        };
      };
    };
    for (int k1 = 0; k1 < 10; k1++) {
      for (int k2 = 0; k2 < 10; k2++) {
        for (int m = 0; m < (1 << shft); m++) {
          for (int j = 0; j < 10; j++) {
            int nz1 = z * j + k1;
            int nk1 = nz1 / 10;
            nz1 %= 10;
            int nz2 = n * j + k2;
            int nk2 = nz2 / 10;
            nz2 %= 10;
            int nmsk = m;
            if (zbt[nz1] != -1) nmsk |= (1 << zbt[nz1]);
            if (nbt[nz2] != -1) nmsk |= (1 << (nbt[nz2] + add));
            if (j < ddiv[i - 1]) {
              dp[nk1][nk2][nmsk][i % 2][0] += dp[k1][k2][m][(i - 1) % 2][0];
              dp[nk1][nk2][nmsk][i % 2][0] += dp[k1][k2][m][(i - 1) % 2][1];
            } else if (j == ddiv[i - 1]) {
              dp[nk1][nk2][nmsk][i % 2][0] += dp[k1][k2][m][(i - 1) % 2][0];
              dp[nk1][nk2][nmsk][i % 2][1] += dp[k1][k2][m][(i - 1) % 2][1];
            } else {
              dp[nk1][nk2][nmsk][i % 2][1] += dp[k1][k2][m][(i - 1) % 2][0];
              dp[nk1][nk2][nmsk][i % 2][1] += dp[k1][k2][m][(i - 1) % 2][1];
            };
            dp[nk1][nk2][nmsk][i % 2][0] %= 998244353ll;
            dp[nk1][nk2][nmsk][i % 2][1] %= 998244353ll;
          };
        };
      };
    };
  };
  long long erg = 0;
  for (int k1 = 0; k1 < 10; k1++) {
    for (int k2 = 0; k2 < 10; k2++) {
      for (int m = 0; m < (1 << shft); m++) {
        for (int i = 0; i < 4; i++) {
          if (m & (1 << i) && m & (1 << (i + add))) {
            erg += dp[k1][k2][m][ddiv.size() % 2][0];
            erg %= 998244353ll;
            break;
          };
        };
      };
    };
  };
  erg = erg + erg;
  erg %= 998244353ll;
  return erg;
};
long long mmd() {
  long long zz = 1;
  long long erg = 0;
  for (int i = 0; i < num.size(); i++) {
    erg += zz * num[i];
    erg %= 998244353ll;
    zz *= 10;
    zz %= 998244353ll;
  };
  return erg;
};
void teil(int j) {
  ddiv.clear();
  int akt;
  int prev = 0;
  for (int i = num.size() - 1; i >= 0; i--) {
    int akt = num[i];
    int dd = 10 * prev + akt;
    ddiv.push_back(dd / j);
    prev = dd % j;
  };
  std::reverse(ddiv.begin(), ddiv.end());
  if (ddiv[ddiv.size() - 1]) ddiv.push_back(0);
};
int main(void) {
  scanf("%s", str);
  int n = strlen(str);
  for (int i = n - 1; i >= 0; i--) {
    num.push_back(str[i] - '0');
  };
  long long erg = mmd();
  for (int i = 1; i < 10; i++) {
    for (int j = i + 1; j < 10; j++) {
      if (gcd(j, i) == 1) {
        teil(j);
        erg += calc(i, j);
        erg %= 998244353ll;
      };
    };
  };
  printf("%lld\n", erg);
  return 0;
};

### Prompt

Your challenge is to write a cpp solution to 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>
#pragma GCC optimize("O3")
int gcd(int a, int b) {
  if (a % b == 0)
    return b;
  else
    return gcd(b, a % b);
};
long long dp[10][10][(1 << 8)][2][2];
int zbt[10];
int nbt[10];
char str[120];
std::vector<int> ddiv;
std::vector<int> num;
long long calc(int z, int n) {
  memset(zbt, -1, sizeof(zbt));
  memset(nbt, -1, sizeof(nbt));
  memset(dp, 0, sizeof(dp));
  int add = 0;
  for (int i = 1; i * n < 10; i++) {
    zbt[i * z] = i - 1;
    nbt[i * n] = i - 1;
    add = i;
  };
  int shft = add * 2;
  dp[0][0][0][0][0] = 1;
  for (int i = 1; i <= ddiv.size(); i++) {
    for (int k1 = 0; k1 < 10; k1++) {
      for (int k2 = 0; k2 < 10; k2++) {
        for (int m = 0; m < (1 << (shft)); m++) {
          dp[k1][k2][m][i % 2][0] = 0;
          dp[k1][k2][m][i % 2][1] = 0;
        };
      };
    };
    for (int k1 = 0; k1 < 10; k1++) {
      for (int k2 = 0; k2 < 10; k2++) {
        for (int m = 0; m < (1 << shft); m++) {
          for (int j = 0; j < 10; j++) {
            int nz1 = z * j + k1;
            int nk1 = nz1 / 10;
            nz1 %= 10;
            int nz2 = n * j + k2;
            int nk2 = nz2 / 10;
            nz2 %= 10;
            int nmsk = m;
            if (zbt[nz1] != -1) nmsk |= (1 << zbt[nz1]);
            if (nbt[nz2] != -1) nmsk |= (1 << (nbt[nz2] + add));
            if (j < ddiv[i - 1]) {
              dp[nk1][nk2][nmsk][i % 2][0] += dp[k1][k2][m][(i - 1) % 2][0];
              dp[nk1][nk2][nmsk][i % 2][0] += dp[k1][k2][m][(i - 1) % 2][1];
            } else if (j == ddiv[i - 1]) {
              dp[nk1][nk2][nmsk][i % 2][0] += dp[k1][k2][m][(i - 1) % 2][0];
              dp[nk1][nk2][nmsk][i % 2][1] += dp[k1][k2][m][(i - 1) % 2][1];
            } else {
              dp[nk1][nk2][nmsk][i % 2][1] += dp[k1][k2][m][(i - 1) % 2][0];
              dp[nk1][nk2][nmsk][i % 2][1] += dp[k1][k2][m][(i - 1) % 2][1];
            };
            dp[nk1][nk2][nmsk][i % 2][0] %= 998244353ll;
            dp[nk1][nk2][nmsk][i % 2][1] %= 998244353ll;
          };
        };
      };
    };
  };
  long long erg = 0;
  for (int k1 = 0; k1 < 10; k1++) {
    for (int k2 = 0; k2 < 10; k2++) {
      for (int m = 0; m < (1 << shft); m++) {
        for (int i = 0; i < 4; i++) {
          if (m & (1 << i) && m & (1 << (i + add))) {
            erg += dp[k1][k2][m][ddiv.size() % 2][0];
            erg %= 998244353ll;
            break;
          };
        };
      };
    };
  };
  erg = erg + erg;
  erg %= 998244353ll;
  return erg;
};
long long mmd() {
  long long zz = 1;
  long long erg = 0;
  for (int i = 0; i < num.size(); i++) {
    erg += zz * num[i];
    erg %= 998244353ll;
    zz *= 10;
    zz %= 998244353ll;
  };
  return erg;
};
void teil(int j) {
  ddiv.clear();
  int akt;
  int prev = 0;
  for (int i = num.size() - 1; i >= 0; i--) {
    int akt = num[i];
    int dd = 10 * prev + akt;
    ddiv.push_back(dd / j);
    prev = dd % j;
  };
  std::reverse(ddiv.begin(), ddiv.end());
  if (ddiv[ddiv.size() - 1]) ddiv.push_back(0);
};
int main(void) {
  scanf("%s", str);
  int n = strlen(str);
  for (int i = n - 1; i >= 0; i--) {
    num.push_back(str[i] - '0');
  };
  long long erg = mmd();
  for (int i = 1; i < 10; i++) {
    for (int j = i + 1; j < 10; j++) {
      if (gcd(j, i) == 1) {
        teil(j);
        erg += calc(i, j);
        erg %= 998244353ll;
      };
    };
  };
  printf("%lld\n", erg);
  return 0;
};

```