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 mo = 998244353;
int len, ans;
int vis1[15], vis2[15];
char n[105];
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
struct state {
  int jw1, jw2;
  int les1, les2;
  int sta1, sta2;
  state() { jw1 = jw2 = les1 = les2 = sta1 = sta2 = 0; }
  bool operator<(const state &a) const {
    if (jw1 != a.jw1) return jw1 < a.jw1;
    if (jw2 != a.jw2) return jw2 < a.jw2;
    if (les1 != a.les1) return les1 < a.les1;
    if (les2 != a.les2) return les2 < a.les2;
    if (sta1 != a.sta1) return sta1 < a.sta1;
    if (sta2 != a.sta2) return sta2 < a.sta2;
    return 0;
  }
  bool operator==(const state &a) const {
    return jw1 == a.jw1 && jw2 == a.jw2 && les1 == a.les1 && les2 == a.les2 &&
           sta1 == a.sta1 && sta2 == a.sta2;
  }
  bool operator!=(const state &a) const {
    return !(jw1 == a.jw1 && jw2 == a.jw2 && les1 == a.les1 && les2 == a.les2 &&
             sta1 == a.sta1 && sta2 == a.sta2);
  }
};
state work(state las, int v1, int v2, int vnow, int bit) {
  state now = las;
  now.jw1 = now.jw1 + v1 * vnow;
  now.jw2 = now.jw2 + v2 * vnow;
  v1 = now.jw1 % 10;
  now.jw1 /= 10;
  v2 = now.jw2 % 10;
  now.jw2 /= 10;
  if (v1 != n[bit]) now.les1 = (v1 < n[bit] ? 0 : 1);
  if (v2 != n[bit]) now.les2 = (v2 < n[bit] ? 0 : 1);
  if (now.sta1 != -1) {
    if (vis1[v1] != -1) now.sta1 |= 1 << vis1[v1];
    if (vis2[v2] != -1) now.sta2 |= 1 << vis2[v2];
    if (now.sta1 & now.sta2) now.sta1 = now.sta2 = -1;
  }
  return now;
}
map<state, int> mp[105];
void solve(int v1, int v2, int val) {
  for (int i = (int)(0); i <= (int)(9); i++) {
    vis1[i] = -1;
    vis2[i] = -1;
  }
  int nd = 0;
  for (int i = (int)(1); i <= (int)(9 / v2); i++) {
    vis1[i * v1] = nd;
    vis2[i * v2] = nd;
    nd++;
  }
  for (int i = (int)(0); i <= (int)(len + 2); i++) mp[i].clear();
  state tmp;
  mp[0][tmp] = 1;
  for (int i = (int)(1); i <= (int)(len + 2); i++)
    for (auto j : mp[i - 1]) {
      state tmp = j.first;
      int val = j.second;
      for (int nowv = (int)(0); nowv <= (int)(9); nowv++) {
        state now = work(tmp, v1, v2, nowv, i);
        mp[i][now] = (mp[i][now] + val) % mo;
      }
    }
  int ans = 0;
  for (auto i : mp[len + 2]) {
    if (i.first.sta1 == -1 && i.first.les1 == 0 && i.first.les2 == 0 &&
        i.first.jw1 == 0 && i.first.jw2 == 0)
      ans = (ans + i.second) % mo;
  }
  ::ans = (::ans + 1ll * val * ans) % mo;
}
int main() {
  scanf("%s", n + 1);
  len = strlen(n + 1);
  reverse(n + 1, n + len + 1);
  for (int i = (int)(1); i <= (int)(len); i++) n[i] -= '0';
  for (int i = (int)(1); i <= (int)(9); i++)
    for (int j = (int)(i); j <= (int)(9); j++)
      if (gcd(i, j) == 1) solve(i, j, (i == j ? 1 : 2));
  printf("%d\n", ans);
}