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>
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int dp[1 << 4][1 << 4][10][10][2], dq[1 << 4][1 << 4][10][10][2];
int solve(int *aa, int n, int p, int q) {
  int i, k, b1, b2, c1, c2, gt, d, ans;
  k = 9 / q;
  for (b1 = 0; b1 < 1 << k; b1++)
    for (b2 = 0; b2 < 1 << k; b2++)
      for (c1 = 0; c1 < 10; c1++)
        for (c2 = 0; c2 < 10; c2++)
          for (gt = 0; gt < 2; gt++) dp[b1][b2][c1][c2][gt] = 0;
  dp[0][0][0][0][0] = 1;
  for (i = n - 1; i >= 0; i--) {
    for (b1 = 0; b1 < 1 << k; b1++)
      for (b2 = 0; b2 < 1 << k; b2++)
        for (c1 = 0; c1 < 10; c1++)
          for (c2 = 0; c2 < 10; c2++)
            for (gt = 0; gt < 2; gt++) dq[b1][b2][c1][c2][gt] = 0;
    for (b1 = 0; b1 < 1 << k; b1++)
      for (b2 = 0; b2 < 1 << k; b2++)
        for (c1 = 0; c1 < 10; c1++)
          for (c2 = 0; c2 < 10; c2++)
            for (gt = 0; gt < 2; gt++) {
              int x = dp[b1][b2][c1][c2][gt];
              if (x == 0) continue;
              for (d = 0; d < 10; d++) {
                int d1, d2, b1_, b2_, c1_, c2_, gt_;
                d1 = (d * p + c1) % 10, d2 = (d * q + c2) % 10;
                b1_ =
                    b1 | (d1 > 0 && d1 % p == 0 && d1 / p <= k ? 1 << d1 / p - 1
                                                               : 0);
                b2_ =
                    b2 | (d2 > 0 && d2 % q == 0 && d2 / q <= k ? 1 << d2 / q - 1
                                                               : 0);
                c1_ = (d * p + c1) / 10, c2_ = (d * q + c2) / 10;
                gt_ = d == aa[i] ? gt : d > aa[i];
                dq[b1_][b2_][c1_][c2_][gt_] =
                    (dq[b1_][b2_][c1_][c2_][gt_] + x) % 998244353;
              }
            }
    for (b1 = 0; b1 < 1 << k; b1++)
      for (b2 = 0; b2 < 1 << k; b2++)
        for (c1 = 0; c1 < 10; c1++)
          for (c2 = 0; c2 < 10; c2++)
            for (gt = 0; gt < 2; gt++)
              dp[b1][b2][c1][c2][gt] = dq[b1][b2][c1][c2][gt];
  }
  ans = 0;
  for (b1 = 0; b1 < 1 << k; b1++)
    for (b2 = 0; b2 < 1 << k; b2++)
      if ((b1 & b2) != 0) ans = (ans + dp[b1][b2][0][0][0]) % 998244353;
  return ans;
}
int main() {
  static char cc[100 + 1];
  static int aa[100];
  int n, i, p, q, ans;
  scanf("%s", cc), n = strlen(cc);
  for (i = 0; i < n; i++) cc[i] -= '0';
  ans = 0;
  for (i = 0; i < n; i++) ans = ((long long)ans * 10 + cc[i]) % 998244353;
  for (q = 2; q <= 9; q++) {
    int a;
    a = 0;
    for (i = 0; i < n; i++) {
      a = a * 10 + cc[i];
      aa[i] = a / q;
      a %= q;
    }
    for (p = 1; p < q; p++)
      if (gcd(p, q) == 1)
        ans = (ans + (long long)solve(aa, n, p, q) * 2) % 998244353;
  }
  printf("%d\n", ans);
  return 0;
}