#include <bits/stdc++.h>
long long dp[205][25][25][25][2], cif[205], n, a, b;
char ch[205];
long long calc(long long k, long long nr, long long m1, long long m2,
               long long ok) {
  if (k > n)
    if (!nr && (m1 & m2))
      return 1;
    else
      return 0;
  long long &rasp = dp[k][nr + 9][m1][m2][ok];
  if (rasp >= 0) return rasp;
  rasp = 0;
  long long x;
  if (ok)
    x = cif[k];
  else
    x = 9;
  long long i, j, aux, a1, a2;
  for (i = 0; i <= x; i++)
    for (j = 0; j <= 9; j++) {
      aux = nr * 10 - i * a + j * b;
      a1 = 0;
      a2 = 0;
      if (aux + b <= 0 || aux >= a) continue;
      if (i && i % b == 0) a1 = 1 << (i / b - 1);
      if (j && j % a == 0 && j / a * b < 10) a2 = 1 << (j / a - 1);
      rasp =
          (rasp + calc(k + 1, aux, m1 | a1, m2 | a2, ok && i == x)) % 998244353;
    }
  return rasp;
}
long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
int main() {
  fgets(ch + 1, 103, stdin);
  n = strlen(ch + 1) - 1;
  long long i;
  for (i = 1; i <= n; i++) cif[i] = ch[i] - '0';
  long long rasp = 0;
  for (i = 1; i <= n; i++) rasp = (rasp * 10 + cif[i]) % 998244353;
  for (a = 1; a <= 9; a++)
    for (b = a + 1; b <= 9; b++)
      if (gcd(a, b) == 1) {
        memset(dp, -1, sizeof(dp));
        rasp = (rasp + calc(1, 0, 0, 0, 1) * 2) % 998244353;
      }
  printf("%lld\n", rasp);
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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>
long long dp[205][25][25][25][2], cif[205], n, a, b;
char ch[205];
long long calc(long long k, long long nr, long long m1, long long m2,
               long long ok) {
  if (k > n)
    if (!nr && (m1 & m2))
      return 1;
    else
      return 0;
  long long &rasp = dp[k][nr + 9][m1][m2][ok];
  if (rasp >= 0) return rasp;
  rasp = 0;
  long long x;
  if (ok)
    x = cif[k];
  else
    x = 9;
  long long i, j, aux, a1, a2;
  for (i = 0; i <= x; i++)
    for (j = 0; j <= 9; j++) {
      aux = nr * 10 - i * a + j * b;
      a1 = 0;
      a2 = 0;
      if (aux + b <= 0 || aux >= a) continue;
      if (i && i % b == 0) a1 = 1 << (i / b - 1);
      if (j && j % a == 0 && j / a * b < 10) a2 = 1 << (j / a - 1);
      rasp =
          (rasp + calc(k + 1, aux, m1 | a1, m2 | a2, ok && i == x)) % 998244353;
    }
  return rasp;
}
long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
int main() {
  fgets(ch + 1, 103, stdin);
  n = strlen(ch + 1) - 1;
  long long i;
  for (i = 1; i <= n; i++) cif[i] = ch[i] - '0';
  long long rasp = 0;
  for (i = 1; i <= n; i++) rasp = (rasp * 10 + cif[i]) % 998244353;
  for (a = 1; a <= 9; a++)
    for (b = a + 1; b <= 9; b++)
      if (gcd(a, b) == 1) {
        memset(dp, -1, sizeof(dp));
        rasp = (rasp + calc(1, 0, 0, 0, 1) * 2) % 998244353;
      }
  printf("%lld\n", rasp);
  return 0;
}

```