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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int d = 10, p = 4, maxn = 103;
const long long mod = 998244353;
void upd(int& a, const int& b) {
  a += b;
  if (a >= mod) a -= mod;
}
int gcd(int a, int b) {
  while (b) {
    int c = b;
    b = a % b;
    a = c;
  }
  return a;
}
string s;
int n;
map<pair<int, int>, int> dp[2][d][d][2];
int count(int up, int down) {
  vector<int> fx(d, 0), fy(d, 0);
  int cnt = 0;
  for (int i = 1; i < d; i++)
    if (i * up < d && i * down < d)
      fx[i * up] = (1 << cnt), fy[i * down] = (1 << cnt), cnt++;
  for (int i = 0; i < d; i++)
    for (int j = 0; j < d; j++)
      for (int k = 0; k < 2; k++) dp[0][i][j][k].clear();
  dp[0][0][0][1][{0, 0}] = 1;
  for (int len = 1; len <= n; len++) {
    for (int i = 0; i < d; i++)
      for (int j = 0; j < d; j++)
        for (int k = 0; k < 2; k++) dp[len & 1][i][j][k].clear();
    for (int cx = 0; cx < d; cx++)
      for (int cy = 0; cy < d; cy++)
        for (int yn = 0; yn < 2; yn++)
          for (pair<pair<int, int>, int> m : dp[!(len & 1)][cx][cy][yn]) {
            for (int di = 0; di < d; di++) {
              int nwdx = cx + di * up, nwdy = cy + di * down;
              bool nwyn = (nwdy % 10 == s[s.size() - len] - '0'
                               ? yn
                               : nwdy % 10 < s[s.size() - len] - '0');
              int nwmx = m.first.first | fx[nwdx % 10],
                  nwmy = m.first.second | fy[nwdy % 10];
              upd(dp[len & 1][nwdx / 10][nwdy / 10][nwyn][{nwmx, nwmy}],
                  m.second);
            }
          }
  }
  int ans = 0;
  for (pair<pair<int, int>, int> m : dp[n & 1][0][0][1])
    if (m.first.first & m.first.second) upd(ans, m.second);
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> s;
  s.insert(s.begin(), '0');
  n = s.size();
  int ans = count(1, 1);
  for (int x = 1; x < d; x++)
    for (int y = x + 1; y < d; y++)
      if (gcd(x, y) == 1) upd(ans, (count(x, y) * 2) % mod);
  cout << ans << "\n";
  return 0;
}