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: /*
  stream Butter!
  eggyHide eggyVengeance
  I need U
  xiao rerun when
   */
  import static java.lang.Math.*;
  import java.util.*;
  import java.io.*;
  import java.math.*;
  
  public class x1559E2
  {
      static final long MOD = 998244353L;
      public static void main(String hi[]) throws Exception
      {
          BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(infile.readLine());
          int N = Integer.parseInt(st.nextToken());
          int M = Integer.parseInt(st.nextToken());
          int[] left = new int[N];
          int[] right = new int[N];
          for(int i=0; i < N; i++)
          {
              st = new StringTokenizer(infile.readLine());
              left[i] = Integer.parseInt(st.nextToken());
              right[i] = Integer.parseInt(st.nextToken());
          }
          long[] ways = new long[M+1];
          outer:for(int v=1; v <= M; v++)
          {
              int CAP = M/v;
              long[] dp = new long[CAP+1];
              dp[0] = 1L;
              for(int t=0; t < N; t++)
              {
                  int min = Integer.MAX_VALUE;
                  int max = 0;
                  for(int i=v; i <= right[t]; i+=v)
                      if(i >= left[t])
                      {
                          min = min(min, i/v);
                          max = i/v;
                      }
                  if(min == Integer.MAX_VALUE)
                      continue outer;
                  long[] psums = new long[CAP+1];
                  psums[0] = dp[0];
                  for(int i=1; i <= CAP; i++)
                  {
                      psums[i] = psums[i-1]+dp[i];
                      if(psums[i] >= MOD)
                          psums[i] -= MOD;
                  }
                  long[] next = new long[CAP+1];
                  for(int i=min; i <= CAP; i++)
                  {
                      int r = i-min;
                      int l = max(0, i-max);
                      next[i] = psums[r];
                      if(l > 0)
                          next[i] -= psums[l-1];
                      if(next[i] < 0)
                          next[i] += MOD;
                  }
                  dp = next;
              }
              for(long x: dp)
              {
                  ways[v] += x;
                  if(ways[v] >= MOD)
                      ways[v] -= MOD;
              }
          }
          for(int d=M; d >= 1; d--)
              for(int v=d+d; v <= M; v+=d)
              {
                  ways[d] -= ways[v];
                  if(ways[d] < 0)
                      ways[d] += MOD;
              }
          System.out.println(ways[1]%MOD);
      }
      public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception
      {
          int[] arr = new int[N];
          st = new StringTokenizer(infile.readLine());
          for(int i=0; i < N; i++)
              arr[i] = Integer.parseInt(st.nextToken());
          return arr;
      }
  }
  /*
  dp_g[m] = # of ways to choose N stars such that sum = m and gcd is divisible by g
   */