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.io.*;
  import java.util.*;
   
  public class Main extends PrintWriter {
      
      long M = 998244353L;
      
      void solve() {
          int n = sc.nextInt();
          int m = sc.nextInt();
          int[] l = new int[n];
          int[] r = new int[n];
          for(int i = 0; i < n; i++) {
              l[i] = sc.nextInt();
              r[i] = sc.nextInt();
          }
          long[] ans = new long[m+1];
          for(int d = m; d >= 1; d--) {
              int t = m / d;
              long[] dp = new long[t+1];
              long[] pre = new long[t+1];
              dp[0] = 1L;
              Arrays.fill(pre, 1L);
              for(int j = 0; j < n; j++) {
                  int ll = (l[j]+d-1)/d;
                  int rr = r[j]/d;
                  for(int k = 0; k <= t; k++) {
                      dp[k] = (k-ll<0?0L:pre[k-ll]) - (k-rr-1<0?0L:pre[k-rr-1]);
                      if(dp[k] < 0) dp[k] += M;
                  }
                  long sum = 0L;
                  for(int k = 0; k <= t; k++) {
                      sum += dp[k];
                      if(sum >= M) sum -= M;
                      pre[k] = sum;
                  }
              }
              ans[d] = pre[t]; 
              for(int j = 2*d; j <= m; j += d) {
                  ans[d] -= ans[j];
                  if(ans[d] < 0) ans[d] += M;
              }
          }
          println(ans[1]);
      }
      
  //  Main() throws FileNotFoundException { super(new File("output.txt")); }
  //  InputReader sc = new InputReader(new FileInputStream("test_input.txt"));
    Main() { super(System.out); }
    InputReader sc = new InputReader(System.in);
    static class InputReader {
        InputReader(InputStream in) { this.in = in; } InputStream in;
        
        private byte[] buf = new byte[16384];
        private int    curChar;
        private int    numChars;
        
   
        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
   /*
        private String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }*/
   
        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
   
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
   
        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
   
        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
   
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
   
      public static void main(String[] $) {
          new Thread(null, new Runnable() {
              public void run() {
                  long start = System.nanoTime();
                  try {Main solution = new Main(); solution.solve(); solution.flush();} 
                  catch (Exception e) {e.printStackTrace(); System.exit(1);}
                  System.err.println((System.nanoTime()-start)/1E9);
              }
          }, "1", 1 << 27).start();
   
      }
  }