#include <bits/stdc++.h>
const int mu = 998244353;
int n, f[102][1 << 9][1 << 5][2][20], x, y, ans;
char s[105];
void reduce(int &x) { x += x >> 31 & mu; }
int gcd(int x, int y) {
  if (x % y == 0) return y;
  return gcd(y, x % y);
}
int dfs(int t, int s1, int s2, int flag, int p) {
  if (t > n) return (s1 & s2) && (p == 0);
  int &ret = f[t][s1][s2][flag][p + 9];
  if (ret != -1) return ret;
  ret = 0;
  int up;
  if (flag == 0)
    up = 9;
  else
    up = s[t] - '0';
  for (int i = 0; i <= up; i++)
    for (int j = 0; j <= 9; j++) {
      int tt = p * 10 + i * y - j * x;
      if (tt <= -y || tt >= x) continue;
      int t1 = s1, t2 = s2;
      if (i && i % x == 0) t1 |= 1 << (i / x - 1);
      if (j && j % y == 0 && j / y * x < 10) t2 |= 1 << (j / y - 1);
      reduce(ret += dfs(t + 1, t1, t2, flag & (i == up), tt) - mu);
    }
  return ret;
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) ans = (ans * 10ll + s[i] - '0') % mu;
  for (x = 1; x <= 9; x++)
    for (y = 1; y < x; y++)
      if (gcd(x, y) == 1) {
        memset(f, -1, sizeof(f));
        ans = (ans + dfs(1, 0, 0, 1, 0) * 2ll) % mu;
      }
  printf("%d\n", ans);
}

### 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>
const int mu = 998244353;
int n, f[102][1 << 9][1 << 5][2][20], x, y, ans;
char s[105];
void reduce(int &x) { x += x >> 31 & mu; }
int gcd(int x, int y) {
  if (x % y == 0) return y;
  return gcd(y, x % y);
}
int dfs(int t, int s1, int s2, int flag, int p) {
  if (t > n) return (s1 & s2) && (p == 0);
  int &ret = f[t][s1][s2][flag][p + 9];
  if (ret != -1) return ret;
  ret = 0;
  int up;
  if (flag == 0)
    up = 9;
  else
    up = s[t] - '0';
  for (int i = 0; i <= up; i++)
    for (int j = 0; j <= 9; j++) {
      int tt = p * 10 + i * y - j * x;
      if (tt <= -y || tt >= x) continue;
      int t1 = s1, t2 = s2;
      if (i && i % x == 0) t1 |= 1 << (i / x - 1);
      if (j && j % y == 0 && j / y * x < 10) t2 |= 1 << (j / y - 1);
      reduce(ret += dfs(t + 1, t1, t2, flag & (i == up), tt) - mu);
    }
  return ret;
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) ans = (ans * 10ll + s[i] - '0') % mu;
  for (x = 1; x <= 9; x++)
    for (y = 1; y < x; y++)
      if (gcd(x, y) == 1) {
        memset(f, -1, sizeof(f));
        ans = (ans + dfs(1, 0, 0, 1, 0) * 2ll) % mu;
      }
  printf("%d\n", ans);
}

```