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>
using namespace std;
string n;
long long dp[101][10][10][16][16][2][2], mpx[20], mpy[20];
long long mod = 998244353;
long long solve_dp(int k1, int k2) {
  memset(dp, 0, sizeof(dp));
  memset(mpx, 0, sizeof(mpx));
  memset(mpy, 0, sizeof(mpy));
  dp[0][0][0][0][0][1][1] = 1;
  int h = 0;
  for (int i = 1; k1 * i < 10 && k2 * i < 10; i++)
    mpx[k1 * i] = ++h, mpy[k2 * i] = h;
  h = 1 << h;
  for (int size = 0; size < n.length(); size++)
    for (int c1 = 0; c1 < 9; c1++)
      for (int c2 = 0; c2 < 9; c2++)
        for (int m1 = 0; m1 < h; m1++)
          for (int m2 = 0; m2 < h; m2++)
            for (int sm1 = 0; sm1 < 2; sm1++)
              for (int sm2 = 0; sm2 < 2; sm2++)
                for (int d = 0; d < 10; d++) {
                  int r1 = d * k1 + c1, r2 = d * k2 + c2;
                  int cf1 = r1 / 10, cf2 = r2 / 10;
                  r1 %= 10;
                  r2 %= 10;
                  int mk1 = m1, mk2 = m2;
                  if (mpx[r1] != 0) mk1 = mk1 | (1 << (mpx[r1] - 1));
                  if (mpy[r2] != 0) mk2 = mk2 | (1 << (mpy[r2] - 1));
                  int s1 = sm1, s2 = sm2;
                  if (r1 + 48 < n[n.length() - size - 1])
                    s1 = 1;
                  else if (r1 + 48 > n[n.length() - size - 1])
                    s1 = 0;
                  if (r2 + 48 < n[n.length() - size - 1])
                    s2 = 1;
                  else if (r2 + 48 > n[n.length() - size - 1])
                    s2 = 0;
                  dp[size + 1][cf1][cf2][mk1][mk2][s1][s2] +=
                      dp[size][c1][c2][m1][m2][sm1][sm2];
                  dp[size + 1][cf1][cf2][mk1][mk2][s1][s2] %= mod;
                }
  long long sol = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < h; j++)
      if ((i & j) != 0) sol += dp[n.length()][0][0][i][j][1][1], sol %= mod;
  }
  return sol;
}
int gcd(int a, int b) {
  int c;
  while (b) {
    c = a % b;
    a = b;
    b = c;
  }
  return a;
}
int main() {
  cin >> n;
  long long sol = 0, s = 0;
  for (int i = 0; i < n.length(); i++) s = (s * 10 + n[i] - 48) % mod;
  for (int i = 1; i < 10; i++) {
    for (int j = 1; j < i; j++) {
      if (gcd(i, j) == 1) sol = (sol + solve_dp(i, j)) % mod;
    }
  }
  cout << (sol * 2 + s) % mod;
  return 0;
}