#include <bits/stdc++.h>
using namespace std;
const long long maxx = 100000 + 7;
const long long maxn = 100 + 7;
const long long mod = 998244353;
const long long maxs = 5 * (1E5) + 7;
const long long maxm = 30 + 7;
const long long maxk = 800 + 7;
const long long maxw = 100 + 7;
const long long maxh = 100 + 7;
const double pi = 3.1415926535898;
const int inf = 1e9 + 7;
const double eps = 1e-8;
ostream &operator<<(ostream &os, pair<long long, long long> &rhs) {
  os << rhs.first << " " << rhs.second << endl;
  return os;
}
long long qw(long long a, long long b) {
  long long ans = 1;
  if (a == 0) return 0ll;
  while (b) {
    if (b & 1) {
      ans = (ans % mod * a % mod) % mod;
      ans %= mod;
    }
    b >>= 1;
    a = (a % mod * a % mod) % mod;
    a %= mod;
  }
  ans %= mod;
  return ans;
}
template <class T>
T min3(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
T max3(T a, T b, T c) {
  return max(max(a, b), c);
}
long long dp[maxn][100 | 1][2][1 << 4][1 << 4];
long long vis[maxn][100 | 1][2][1 << 4][1 << 4];
long long dig[maxn];
long long ncase;
long long n;
long long dfs(long long pos, long long dt, long long limit, long long mx,
              long long my, long long x, long long y) {
  if (pos == n) return (dt == 0) && (my & mx);
  long long &ans = dp[pos][dt + x][limit][mx][my];
  if (vis[pos][dt + x][limit][mx][my] == ncase) return ans;
  vis[pos][dt + x][limit][mx][my] = ncase;
  long long up = limit ? dig[pos] : 9;
  ans = 0;
  for (int i = (0); i <= (9); i++) {
    for (int j = (0); j <= (up); j++) {
      long long ndt = dt * 10 - i * y + j * x;
      if (ndt <= -x || ndt >= y) continue;
      long long tmx = 0, tmy = 0;
      if ((j != 0) && (j % y == 0)) tmy = (1 << ((j / y) - 1));
      if ((i != 0) && (i % x == 0) && ((i / x) * y <= 9))
        tmx = (1 << ((i / x) - 1));
      ans +=
          dfs(pos + 1, ndt, limit && (j == up), mx | tmx, my | tmy, x, y) % mod;
      ans %= mod;
    }
  }
  ans %= mod;
  return ans;
}
string str;
long long ans = 0;
void init() {
  n = str.length();
  ans = 0;
  for (long long i = (0); i < (str.length()); i++) {
    dig[i] = str[i] - '0';
    ans = (ans * 10 + dig[i]) % mod;
  }
}
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
void solve() {
  ncase = 0;
  for (int x = (1); x <= (9); x++)
    for (int y = (x + 1); y <= (9); y++)
      if (gcd(x, y) == 1)
        ++ncase, ans += 2 * dfs(0, 0, 1, 0, 0, x, y) % mod, ans %= mod;
  cout << ans << endl;
}
int main(void) {
  while (cin >> str) {
    init();
    solve();
  }
}

### 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>
using namespace std;
const long long maxx = 100000 + 7;
const long long maxn = 100 + 7;
const long long mod = 998244353;
const long long maxs = 5 * (1E5) + 7;
const long long maxm = 30 + 7;
const long long maxk = 800 + 7;
const long long maxw = 100 + 7;
const long long maxh = 100 + 7;
const double pi = 3.1415926535898;
const int inf = 1e9 + 7;
const double eps = 1e-8;
ostream &operator<<(ostream &os, pair<long long, long long> &rhs) {
  os << rhs.first << " " << rhs.second << endl;
  return os;
}
long long qw(long long a, long long b) {
  long long ans = 1;
  if (a == 0) return 0ll;
  while (b) {
    if (b & 1) {
      ans = (ans % mod * a % mod) % mod;
      ans %= mod;
    }
    b >>= 1;
    a = (a % mod * a % mod) % mod;
    a %= mod;
  }
  ans %= mod;
  return ans;
}
template <class T>
T min3(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
T max3(T a, T b, T c) {
  return max(max(a, b), c);
}
long long dp[maxn][100 | 1][2][1 << 4][1 << 4];
long long vis[maxn][100 | 1][2][1 << 4][1 << 4];
long long dig[maxn];
long long ncase;
long long n;
long long dfs(long long pos, long long dt, long long limit, long long mx,
              long long my, long long x, long long y) {
  if (pos == n) return (dt == 0) && (my & mx);
  long long &ans = dp[pos][dt + x][limit][mx][my];
  if (vis[pos][dt + x][limit][mx][my] == ncase) return ans;
  vis[pos][dt + x][limit][mx][my] = ncase;
  long long up = limit ? dig[pos] : 9;
  ans = 0;
  for (int i = (0); i <= (9); i++) {
    for (int j = (0); j <= (up); j++) {
      long long ndt = dt * 10 - i * y + j * x;
      if (ndt <= -x || ndt >= y) continue;
      long long tmx = 0, tmy = 0;
      if ((j != 0) && (j % y == 0)) tmy = (1 << ((j / y) - 1));
      if ((i != 0) && (i % x == 0) && ((i / x) * y <= 9))
        tmx = (1 << ((i / x) - 1));
      ans +=
          dfs(pos + 1, ndt, limit && (j == up), mx | tmx, my | tmy, x, y) % mod;
      ans %= mod;
    }
  }
  ans %= mod;
  return ans;
}
string str;
long long ans = 0;
void init() {
  n = str.length();
  ans = 0;
  for (long long i = (0); i < (str.length()); i++) {
    dig[i] = str[i] - '0';
    ans = (ans * 10 + dig[i]) % mod;
  }
}
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
void solve() {
  ncase = 0;
  for (int x = (1); x <= (9); x++)
    for (int y = (x + 1); y <= (9); y++)
      if (gcd(x, y) == 1)
        ++ncase, ans += 2 * dfs(0, 0, 1, 0, 0, x, y) % mod, ans %= mod;
  cout << ans << endl;
}
int main(void) {
  while (cin >> str) {
    init();
    solve();
  }
}

```