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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const long long MOD = 998244353;
int num[101], L;
char str[101];
long long f[101][2][2][16][16][21], O;
int gcd(int x, int y) {
  int r;
  while (y) {
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}
int main() {
  scanf("%s", str);
  for (int i = 0; str[i]; i++) num[++L] = str[i] - '0';
  std::reverse(num + 1, num + L + 1);
  for (int i = 1; i <= 9; i++)
    for (int j = 1; j <= 9; j++)
      if (gcd(i, j) == 1)
        if (i == 1 && j == 1) {
          long long t = 0;
          for (int k = L; k; k--) t = (t * 10 + num[k]) % MOD;
          O = (O + t) % MOD;
        } else {
          int V = 9 / std::max(i, j);
          for (int k = 0; k < 2; k++)
            for (int l = 0; l < 2; l++)
              for (int m = 0; m < 1 << V; m++)
                for (int n = 0; n < 1 << V; n++)
                  for (int o = -10; o <= 10; o++)
                    f[0][k][l][m][n][o + 10] = o == 0 && (m & n) > 0;
          for (int k = 1; k <= L; k++)
            for (int l = 0; l < 2; l++)
              for (int m = 0; m < 2; m++)
                for (int n = 0; n < 1 << V; n++)
                  for (int o = 0; o < 1 << V; o++)
                    for (int p = -10; p <= 10; p++)
                      f[k][l][m][n][o][p + 10] = 0;
          for (int k = 1; k <= L; k++)
            for (int p = -10; p <= 10; p++)
              for (int d1 = 0; d1 <= 9; d1++)
                for (int d2 = 0; d2 <= 9; d2++) {
                  int c = p * 10 + d2 * i - d1 * j;
                  if (-10 <= c && c <= 10)
                    for (int l = 0; l < 2; l++)
                      if (l == 0 || d1 <= num[k])
                        for (int m = 0; m < 2; m++)
                          if (m == 0 || d2 <= num[k])
                            for (int n = 0; n < 1 << V; n++)
                              for (int o = 0; o < 1 << V; o++)
                                f[k][l][m][n][o][p + 10] =
                                    (f[k][l][m][n][o][p + 10] +
                                     f[k - 1][l & (d1 == num[k])]
                                      [m & (d2 == num[k])]
                                      [n |
                                       (d1 % i == 0 && d1 / i <= V && d1 != 0
                                            ? 1 << d1 / i - 1
                                            : 0)]
                                      [o |
                                       (d2 % j == 0 && d2 / j <= V && d2 != 0
                                            ? 1 << d2 / j - 1
                                            : 0)][c + 10]) %
                                    MOD;
                }
          O = (O + f[L][1][1][0][0][10]) % MOD;
        }
  printf("%lld\n", O);
  return 0;
}