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.ArrayList;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  import java.util.List;
   import java.util.*;
   public class realfast implements Runnable 
    {
      private static final int INF = (int) 1e9;
      long in=  998244353;
      long fac[]= new long[1000001];
      long inv[]=new long[1000001];
      public  void solve() throws IOException 
      {
         
         int n = readInt();
         int m = readInt();
         int l[]=new int[n+1];
         int r[]=new int[n+1];
         for(int i =1;i<=n;i++)
         {
            l[i]=readInt();
            r[i]= readInt();
         }
        long dp[][]=new long[n+1][m+1];
  
        int ul[]=new int[n+1];
        int pl[]=new int[n+1];
  
        ArrayList<Integer> div = new ArrayList<Integer>();
  
  
        for(int i=1;i<=m;i++)
        {
          if(m%i==0)
          {
              div.add(i);
          }
        }
        long val[]=new long[m+1];
  
        for(int i= 0;i<m;i++)
        {
          int g = i+1;
          int  sum = m/g;
          boolean check = true;
  
          for(int j=1;j<=n;j++)
          {
              ul[j]= l[j]/g;
              if((l[j]%g)!=0)
                  ul[j]++;
              pl[j]= r[j]/g;
              if(ul[j]>pl[j])
              {
                  check=false;
                  break;
              }
          }
         // out.println(check);
          if(!check)
          {
              val[i+1]=0;
  
          }
          else
              val[i+1]= val(dp,n,sum,ul,pl);
        }
        /*for(int i =0;i<3;i++)
          out.print(val[i]+" ");
        out.println();*/
        for(int i=m;i>=1;i--)
        {
          for(int j=2*i;j<=m;j=j+i)
          {
              val[i]= (val[i]-val[j]+in)%in;
          }
        }
  
  
  
  
        out.println(val[1]);
  
  
  
  
  
              
         
  
      }
  
      public long val (long dp[][] , int n , int sum , int l[] , int r[] )
      {
          for(int i=1;i<=sum;i++)
         if(i>=l[1]&&i<=r[1])
           dp[1][i]=1;
         else
           dp[1][i]=0;
         long scum[]=new long[sum+1];
          dp[1][0]=0;
      //   out.println(l[1]+" "+r[1]);
         for(int i=2;i<=n;i++)
         {
          scum[0]=0;
          for(int j=1;j<=sum;j++)
           scum[j]= (scum[j-1]+dp[i-1][j])%in;
           for(int j=1;j<=sum;j++)
           {
             int kal = Math.max(j-r[i]-1,0);
             int pal = Math.max(j-l[i],0);
           /*  if(sum==2){
              out.println(kal+" "+pal);
              out.println(l[i]+"lklkl "+r[i]);
             }*/
             dp[i][j]= ((scum[pal])-(scum[kal])+in)%in;
           }
         }
         scum[0]=0;
         for(int j=1;j<=sum;j++)
           scum[j]= (scum[j-1]+dp[n][j])%in;
       
        return scum[sum];
  
      }
      
     
      public long query(long seg[] , int left, int right , int index, int l , int r)
      {   
           long inf = 100000000;
           inf = inf*inf;
          if(left>=l&&right<=r)
          {
              return seg[index];
          }
          if(l>right||left>r)
              return inf;
          int mid = left+(right-left)/2;
          return Math.min(query(seg,left,mid,2*index+1,l,r),query(seg,mid+1,right,2*index+2,l,r));
  
      }
      
      public int value (int seg[], int left , int right ,int index, int l, int r)
      {
              
              if(left>right)
              {
                return -100000000;
              }
              if(right<l||left>r)
                  return -100000000;
              if(left>=l&&right<=r)
                  return seg[index];
              int mid = left+(right-left)/2;
              int val = value(seg,left,mid,2*index+1,l,r);
              int val2 = value(seg,mid+1,right,2*index+2,l,r);
              return Math.max(val,val2);
  
      }
     
      public int gcd(int a , int b )
      {
        if(a<b)
        {
          int t =a;
          a=b;
          b=t;
        }
        if(a%b==0)
          return b ;
        return gcd(b,a%b);
      }
      public long pow(long n , long p,long m)
      {
           if(p==0)
              return 1;
          long val = pow(n,p/2,m);;
          val= (val*val)%m;
          if(p%2==0)
              return val;
          else
              return (val*n)%m;
      }
      
      
      ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
      public static void main(String[] args) {
          new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
      }
   
      private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
      private BufferedReader reader;
      private StringTokenizer tokenizer;
      private PrintWriter out;
   
      @Override
      public void run() {
          try {
              if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                  reader = new BufferedReader(new InputStreamReader(System.in));
                  out = new PrintWriter(System.out);
              } else {
                  reader = new BufferedReader(new FileReader("input.txt"));
                  out = new PrintWriter("output.txt");
              }
              solve();
          } catch (IOException e) {
              throw new RuntimeException(e);
          } finally {
              try {
                  reader.close();
              } catch (IOException e) {
                  // nothing
              }
              out.close();
          }
      }
   
      private String readString() throws IOException {
          while (tokenizer == null || !tokenizer.hasMoreTokens()) {
              tokenizer = new StringTokenizer(reader.readLine());
          }
          return tokenizer.nextToken();
      }
   
      @SuppressWarnings("unused")
      private int readInt() throws IOException {
          return Integer.parseInt(readString());
      }
   
      @SuppressWarnings("unused")
      private long readLong() throws IOException {
          return Long.parseLong(readString());
      }
   
      @SuppressWarnings("unused")
      private double readDouble() throws IOException {
          return Double.parseDouble(readString());
      }
  }
  class edge implements Comparable<edge>{
      int u ;
      int v;
      
      edge(int  u, int v)
      {
         this.u=u;
         this.v=v;
      }
      public int compareTo(edge e)
      {
          return this.v-e.v;
      }
  }