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 Mod = 998244353;
struct State {
  int c1, c2;
  int m1, m2;
  int v1, v2;
  State() { c1 = c2 = m1 = m2 = v1 = v2 = 0; }
  void fix() {
    if (m1 & m2) m1 = m2 = 1;
    return;
  }
  bool check() { return !c1 && !c2 && (m1 & m2) && !v1 && !v2; }
};
bool check(State s) { return s.check(); }
bool operator<(const State& a, const State& b) {
  if (a.c1 != b.c1) return a.c1 < b.c1;
  if (a.c2 != b.c2) return a.c2 < b.c2;
  if (a.m1 != b.m1) return a.m1 < b.m1;
  if (a.m2 != b.m2) return a.m2 < b.m2;
  if (a.v1 != b.v1) return a.v1 < b.v1;
  if (a.v2 != b.v2) return a.v2 < b.v2;
  return false;
}
int x, y;
int num1[10], num2[10];
State trans(State s, int v, int a) {
  int a1 = a * x + s.c1;
  int a2 = a * y + s.c2;
  int b1 = a1 % 10, b2 = a2 % 10;
  a1 /= 10;
  a2 /= 10;
  if (num1[b1] != -1) s.m1 |= 1 << num1[b1];
  if (num2[b2] != -1) s.m2 |= 1 << num2[b2];
  if (b1 < v) s.v1 = 0;
  if (b1 > v) s.v1 = 1;
  if (b2 < v) s.v2 = 0;
  if (b2 > v) s.v2 = 1;
  s.c1 = a1;
  s.c2 = a2;
  s.fix();
  return s;
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int n;
int a[110];
char st[110];
int solve(int xx, int yy) {
  x = xx;
  y = yy;
  memset(num1, -1, sizeof(num1));
  memset(num2, -1, sizeof(num2));
  int cur = 0;
  while (xx < 10 && yy < 10) {
    num1[xx] = cur;
    num2[yy] = cur;
    cur++;
    xx += x;
    yy += y;
  }
  map<State, int> f, g;
  f[State()] = 1;
  for (int i = 1; i <= n; i++) {
    for (map<State, int>::iterator it = f.begin(); it != f.end(); it++)
      for (int k = 0; k < 10; k++) {
        State to = trans(it->first, a[i], k);
        g[to] = (g[to] + (it->second)) % Mod;
      }
    f = g;
    g.clear();
  }
  int ans = 0;
  for (map<State, int>::iterator it = f.begin(); it != f.end(); it++)
    if (check(it->first)) ans = (ans + (it->second)) % Mod;
  return ans;
}
int main() {
  scanf("%s", st);
  n = strlen(st);
  for (int i = 1; i <= n; i++) a[i] = st[n - i] - '0';
  int ans = 0;
  for (int i = 1; i < 10; i++)
    for (int j = 1; j < 10; j++)
      if (gcd(i, j) == 1) ans = (ans + solve(i, j)) % Mod;
  printf("%d\n", ans);
  return 0;
}