#include <bits/stdc++.h>
const int MOD = 998244353;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
std::string N;
int num, den;
int dp[101][20][2][1 << 4][1 << 4];
int solve(int index, int rem, int qr, int aseen, int bseen) {
  if (index == N.size()) {
    return rem == 0 && (aseen & bseen);
  }
  if (rem < -den || rem > num) return 0;
  int& res = dp[index][rem + den][qr][aseen][bseen];
  if (res != -1) {
    return res;
  }
  res = 0;
  for (int a = 0; a < 10; a++) {
    for (int b = 0; b < 10; b++) {
      if (!qr && b > N[index] - '0') continue;
      int aseen2 = aseen, bseen2 = bseen;
      if (a > 0 && a % num == 0) aseen2 |= (1 << (a / num - 1));
      if (b > 0 && b % den == 0) bseen2 |= (1 << (b / den - 1));
      res = (res + solve(index + 1, rem * 10 + den * a - num * b,
                         qr || (b < N[index] - '0'), aseen2 & 15, bseen2)) %
            MOD;
    }
  }
  return res;
}
int main() {
  std::cin >> N;
  int ans = 0;
  for (int i = 0; i < N.size(); i++) {
    ans = (ans * 10LL + (N[i] - '0')) % MOD;
  }
  for (num = 1; num <= 9; num++) {
    for (den = num + 1; den <= 9; den++) {
      if (gcd(num, den) != 1) continue;
      memset(dp, -1, sizeof(dp));
      int tmp = solve(0, 0, 0, 0, 0);
      ans = (ans + tmp * 2LL) % MOD;
    }
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 MOD = 998244353;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
std::string N;
int num, den;
int dp[101][20][2][1 << 4][1 << 4];
int solve(int index, int rem, int qr, int aseen, int bseen) {
  if (index == N.size()) {
    return rem == 0 && (aseen & bseen);
  }
  if (rem < -den || rem > num) return 0;
  int& res = dp[index][rem + den][qr][aseen][bseen];
  if (res != -1) {
    return res;
  }
  res = 0;
  for (int a = 0; a < 10; a++) {
    for (int b = 0; b < 10; b++) {
      if (!qr && b > N[index] - '0') continue;
      int aseen2 = aseen, bseen2 = bseen;
      if (a > 0 && a % num == 0) aseen2 |= (1 << (a / num - 1));
      if (b > 0 && b % den == 0) bseen2 |= (1 << (b / den - 1));
      res = (res + solve(index + 1, rem * 10 + den * a - num * b,
                         qr || (b < N[index] - '0'), aseen2 & 15, bseen2)) %
            MOD;
    }
  }
  return res;
}
int main() {
  std::cin >> N;
  int ans = 0;
  for (int i = 0; i < N.size(); i++) {
    ans = (ans * 10LL + (N[i] - '0')) % MOD;
  }
  for (num = 1; num <= 9; num++) {
    for (den = num + 1; den <= 9; den++) {
      if (gcd(num, den) != 1) continue;
      memset(dp, -1, sizeof(dp));
      int tmp = solve(0, 0, 0, 0, 0);
      ans = (ans + tmp * 2LL) % MOD;
    }
  }
  printf("%d\n", ans);
  return 0;
}

```