#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 2;
const int logn = 20 + 2;
const int mod = 998244353;
char str[maxn];
int x, y, len, ans;
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
int change(char ch) { return ch - '0'; }
int dp[maxn][logn][logn][logn][2];
int DP(int pos, int pre, int state1, int state2, bool limit) {
  if (pos > len) return !pre && (state1 & state2);
  int &ret = dp[pos][pre + x][state1][state2][limit];
  if (~ret) return ret;
  ret = 0;
  int up = !limit ? change(str[pos]) : 9;
  for (int i = 0; i <= 9; i++)
    for (int j = 0; j <= up; j++) {
      int now = pre * 10 - i * y + j * x, st1 = 0, st2 = 0;
      if (now <= -x || now >= y) continue;
      if (i && !(i % x) && i <= 9 / y * x) st1 = 1 << (i / x - 1);
      if (j && !(j % y)) st2 = 1 << (j / y - 1);
      ret = (ret + DP(pos + 1, now, state1 | st1, state2 | st2,
                      limit | (j < change(str[pos])))) %
            mod;
    }
  return ret;
}
int main() {
  scanf("%s", str + 1);
  len = strlen(str + 1);
  for (int i = 1; i <= len; i++) ans = (ans * 10LL + change(str[i])) % mod;
  for (x = 1; x <= 8; x++)
    for (y = x + 1; y <= 9; y++)
      if (gcd(x, y) == 1) {
        memset(dp, -1, sizeof(dp));
        ans = (ans + 2LL * DP(1, 0, 0, 0, false)) % mod;
      }
  printf("%d", ans);
  return 0;
}

### Prompt

Create a solution in Cpp for 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>
using namespace std;
const int maxn = 100 + 2;
const int logn = 20 + 2;
const int mod = 998244353;
char str[maxn];
int x, y, len, ans;
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
int change(char ch) { return ch - '0'; }
int dp[maxn][logn][logn][logn][2];
int DP(int pos, int pre, int state1, int state2, bool limit) {
  if (pos > len) return !pre && (state1 & state2);
  int &ret = dp[pos][pre + x][state1][state2][limit];
  if (~ret) return ret;
  ret = 0;
  int up = !limit ? change(str[pos]) : 9;
  for (int i = 0; i <= 9; i++)
    for (int j = 0; j <= up; j++) {
      int now = pre * 10 - i * y + j * x, st1 = 0, st2 = 0;
      if (now <= -x || now >= y) continue;
      if (i && !(i % x) && i <= 9 / y * x) st1 = 1 << (i / x - 1);
      if (j && !(j % y)) st2 = 1 << (j / y - 1);
      ret = (ret + DP(pos + 1, now, state1 | st1, state2 | st2,
                      limit | (j < change(str[pos])))) %
            mod;
    }
  return ret;
}
int main() {
  scanf("%s", str + 1);
  len = strlen(str + 1);
  for (int i = 1; i <= len; i++) ans = (ans * 10LL + change(str[i])) % mod;
  for (x = 1; x <= 8; x++)
    for (y = x + 1; y <= 9; y++)
      if (gcd(x, y) == 1) {
        memset(dp, -1, sizeof(dp));
        ans = (ans + 2LL * DP(1, 0, 0, 0, false)) % mod;
      }
  printf("%d", ans);
  return 0;
}

```