description: Mocha wants to be an astrologer. There are n stars which can be seen in Zhijiang, and the brightness of the i-th star is a_i. 
  
  Mocha considers that these n stars form a constellation, and she uses (a_1,a_2,…,a_n) to show its state. A state is called mathematical if all of the following three conditions are satisfied:
  
    * For all i (1≤ i≤ n), a_i is an integer in the range [l_i, r_i].
    * ∑  _{i=1} ^ n a_i ≤ m.
    * \gcd(a_1,a_2,…,a_n)=1.
  
  
  
  Here, \gcd(a_1,a_2,…,a_n) denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers a_1,a_2,…,a_n.
  
  Mocha is wondering how many different mathematical states of this constellation exist. Because the answer may be large, you must find it modulo 998 244 353.
  
  Two states (a_1,a_2,…,a_n) and (b_1,b_2,…,b_n) are considered different if there exists i (1≤ i≤ n) such that a_i ≠ b_i.
  
  Input
  
  The first line contains two integers n and m (2 ≤ n ≤ 50, 1 ≤ m ≤ 10^5) — the number of stars and the upper bound of the sum of the brightness of stars.
  
  Each of the next n lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ m) — the range of the brightness of the i-th star.
  
  Output
  
  Print a single integer — the number of different mathematical states of this constellation, modulo 998 244 353.
  
  Examples
  
  Input
  
  
  2 4
  1 3
  1 2
  
  
  Output
  
  
  4
  
  Input
  
  
  5 10
  1 10
  1 10
  1 10
  1 10
  1 10
  
  
  Output
  
  
  251
  
  Input
  
  
  5 100
  1 94
  1 96
  1 91
  4 96
  6 97
  
  
  Output
  
  
  47464146
  
  Note
  
  In the first example, there are 4 different mathematical states of this constellation:
  
    * a_1=1, a_2=1.
    * a_1=1, a_2=2.
    * a_1=2, a_2=1.
    * a_1=3, a_2=1.
solution: import java.util.*;
  import java.io.*;
  public class MochaAndStars {
      public static void main(String[] args) throws IOException {
          Reader in = new Reader();
          PrintWriter out = new PrintWriter(System.out);
          
          int mod = 998244353;
          int N = in.nextInt(), K = in.nextInt();
          int[] left = new int[N], right = new int[N];
          for (int i = 0; i < N; i++) {
              left[i] = in.nextInt();
              right[i] = in.nextInt();
          }
          
          int[] dp2 = new int[K + 1];
          for (int k = 1; k <= K; k++) {
              int M = K / k + 1;
              int[][] dp = new int[N][M];
              for (int i = 0; i < N; i++) {
                  int l = (int)Math.ceil(left[i] / (double)k), r = right[i] / k;
                  if (l > r) {
                      continue;
                  }
                  int current = 0;
                  for (int j = 1; j < M; j++) {
                      if (j - l >= 0) {
                          current += i == 0 ? (j - l == 0 ? 1 : 0) : dp[i - 1][j - l];
                          current %= mod;
                      }
                      if (j - r - 1 >= 0) {
                          current += mod - (i == 0 ? (j - r - 1 == 0 ? 1 : 0) : dp[i - 1][j - r - 1]);
                          current %= mod;
                      }
                      dp[i][j] = current;
                  }
              }
              int sum = 0;
              for (int i : dp[N - 1]) {
                  sum += i;
                  sum %= mod;
              }
              dp2[k] = sum;
          }
          
          for (int i = K; i > 0; i--) {
              for (int j = i * 2; j <= K; j += i) {
                  dp2[i] += mod - dp2[j];
                  dp2[i] %= mod;
              }
          }
          out.println(dp2[1]);
          
          out.close();
      }
      public static int group(int[] group, int i) {
          if (group[i] == i) {
              return i;
          }
          group[i] = group(group, group[i]);
          return group[i];
      }
      static class Reader {
          BufferedReader in;
          StringTokenizer st;
          public Reader() {
              in = new BufferedReader(new InputStreamReader(System.in));
              st = new StringTokenizer("");
          }
          public String nextLine() throws IOException {
              st = new StringTokenizer("");
              return in.readLine();
          }
          public String next() throws IOException {
              while (!st.hasMoreTokens()) {
                  st = new StringTokenizer(in.readLine());
              }
              return st.nextToken();
          }
          public int nextInt() throws IOException {
              return Integer.parseInt(next());
          }
          public long nextLong() throws IOException {
              return Long.parseLong(next());
          }
      }
      public static void sort(int[] arr) {
          List<Integer> list = new ArrayList<>();
          for (int i : arr) {
              list.add(i);
          }
          Collections.sort(list);
          for (int i = 0; i < arr.length; i++) {
              arr[i] = list.get(i);
          }
      }
  }