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: /**
   * check out my youtube channel sh0rkyboy
   * https://tinyurl.com/zdxe2y4z
   * I do screencasts, solutions, and other fun stuff in the future
   */
  
  import java.util.*;
  import java.io.*;
  import static java.lang.Math.min;
  import static java.lang.Math.abs;
  import static java.lang.Math.max;
  public class EdC {
  	static long[] mods = {1000000007, 998244353, 1000000009};
  	static long mod = mods[1];
  	
  	static int[] mu;
  	
  	static int[] isPrime;
  	
  	
  	public static MyScanner sc;
      public static PrintWriter out;
  	public static void main(String[] largewang) throws Exception{
  		// TODO Auto-generated method stub
   		sc = new MyScanner();
   		out = new PrintWriter(System.out);
   		int n = sc.nextInt();
   		
   		int m = sc.nextInt();
   		
   		int[][] intervals = new int[n][2];
   		
   		for(int j =0 ;j<n;j++){
   			intervals[j][0] = sc.nextInt();
   			intervals[j][1] = sc.nextInt();
   			
   		}
   		
   		mobiusAndPrime(100000);
   		long ans = 0;
   		for (int j = 1;j<=100000;j++){
   			boolean found = false;
   			int[][] newOne = new int[n][2];
   			int sum = 0;
   			for(int k = 0;k<n;k++){
   				newOne[k][0] = (intervals[k][0] - 1)/j + 1;
   				sum += newOne[k][0];
   				
   				newOne[k][1] = (intervals[k][1])/j;
   				
   				if (newOne[k][1] < newOne[k][0]){
   					found = true;		
   					break;
   				}
   			}
   			if (found)
   				continue;
   			ans += mu[j]*ans(m/j, newOne, sum);
   			ans %= mod;
   			ans += mod;
   			ans %= mod;
   		}
   		
   		out.println(ans);
   		out.close();
   		
   	}
  	
  	public static long ans(int max, int[][] intervals, int sum) {
  		if (sum > max)
  			return 0;
  		long[] num = new long[max-sum+1];
  		num[0] = 1;
  		for (int j = 0;j<intervals.length;j++){
  //			for(int k = max;k>=0;k--){
  //				 long val = ls.querySum(k,  k);
  //				 if (val != 0){
  //					 ls.update(k+intervals[j][0], min(k+intervals[j][1], max), val); 
  //					 ls.update(k,  k, mod-val);
  //				 }
  //			}
  			
  			
  			int val = intervals[j][1] - intervals[j][0];
  			long cumSum = 0;
  			for (int k = max-sum;k >= max(0, max-sum-val);k--)
  				cumSum += num[k];
  			for (int k = max-sum;k>=0;k--){
  				
  				long prev = num[k];
  				num[k] = cumSum%mod;
  				cumSum -= prev;
  				if (k >= val+1)
  					cumSum += num[k-val-1];
  				cumSum%=mod;
  				cumSum+=mod;
  				cumSum%=mod;
  			}
  		}
  		long finalSum = 0;
  		for(int j = 0;j<=max-sum;j++){
  			finalSum+=num[j];
  			finalSum%=mod;
  		}
  		return finalSum;
  	}
  	public static void mobiusAndPrime(int n){
  		isPrime = new int[n+1];
  		Arrays.fill(isPrime, 1);
  		mu = new int[n+1];
  		Arrays.fill(mu,  1);
  		for(long i = 2;i<=n;i++){
  			if (isPrime[(int)i] == 1){
  				for(long j = i;j<=n;j+=i){
  					if (j > i)
  						isPrime[(int)j] = 0;
  					if (j%(i*i) == 0)
  						mu[(int)j] = 0;
  					mu[(int)j] = -mu[(int)j];
  				}
  			}
  		}
  	}
  	
  	
  	public static void sort(int[] array){
  		ArrayList<Integer> copy = new ArrayList<>();
  		for (int i : array)
  			copy.add(i);
  		Collections.sort(copy);
  		for(int i = 0;i<array.length;i++)
  			array[i] = copy.get(i);
  	}
  	static String[] readArrayString(int n){
  		String[] array = new String[n];
  		for(int j =0 ;j<n;j++)
  			array[j] = sc.next();
  		return array;
  	}
  	static int[] readArrayInt(int n){
      	int[] array = new int[n];
      	for(int j = 0;j<n;j++)
      		array[j] = sc.nextInt();
      	return array;
      }
  	static int[] readArrayInt1(int n){
  		int[] array = new int[n+1];
  		for(int j = 1;j<=n;j++){
  			array[j] = sc.nextInt();
  		}
  		return array;
  	}
  	static long[] readArrayLong(int n){
  		long[] array = new long[n];
  		for(int j =0 ;j<n;j++)
  			array[j] = sc.nextLong();
  		return array;
  	}
  	static double[] readArrayDouble(int n){
  		double[] array = new double[n];
  		for(int j =0 ;j<n;j++)
  			array[j] = sc.nextDouble();
  		return array;
  	}
  	static int minIndex(int[] array){
  		int minValue = Integer.MAX_VALUE;
  		int minIndex = -1;
  		for(int j = 0;j<array.length;j++){
  			if (array[j] < minValue){
  				minValue = array[j];
  				minIndex = j;
  			}
  		}
  		return minIndex;
  	}
  	static int minIndex(long[] array){
  		long minValue = Long.MAX_VALUE;
  		int minIndex = -1;
  		for(int j = 0;j<array.length;j++){
  			if (array[j] < minValue){
  				minValue = array[j];
  				minIndex = j;
  			}
  		}
  		return minIndex;
  	}
  	static int minIndex(double[] array){
  		double minValue = Double.MAX_VALUE;
  		int minIndex = -1;
  		for(int j = 0;j<array.length;j++){
  			if (array[j] < minValue){
  				minValue = array[j];
  				minIndex = j;
  			}
  		}
  		return minIndex;
  	}
  	static long power(long x, long y){
  		if (y == 0)
  			return 1;
  		if (y%2 == 1)
  			return (x*power(x, y-1))%mod;
  		return power((x*x)%mod, y/2)%mod;
  	}
  	static void verdict(boolean a){
          out.println(a ? "YES" : "NO");
      }
      public static class MyScanner {
          BufferedReader br;
          StringTokenizer st;
          public MyScanner() {
              br = new BufferedReader(new InputStreamReader(System.in));
          }
          String next() {
              while (st == null || !st.hasMoreElements()) {
                  try {
                      st = new StringTokenizer(br.readLine());
                  } 
                  catch (IOException e) {
                      e.printStackTrace();
                  }
              }
              return st.nextToken();
          }
          int nextInt() {
              return Integer.parseInt(next());
          }
          long nextLong() {
              return Long.parseLong(next());
          }
          double nextDouble() {
              return Double.parseDouble(next());
          }
          String nextLine() {
              String str = "";
              try{
                  str = br.readLine();
              } 
              catch (IOException e) {
                  e.printStackTrace();
              }
              return str;
          }
          
      }	
      
  
      	static class LazySegmentTree {
      		int size;
      		private long[] sum;
      		private long[] lazy;
      		public LazySegmentTree(long[] array){
      			size = array.length;
      			sum=new long[array.length*4];
      			lazy=new long[array.length*4];
      			buildTree(array,1,0,size-1);
      		}
  
      		private void buildTree(long[] array, int position, int front, int end){
      			//Basis case for returning the elements itself
      			if(front==end){
      				sum[position]=array[front];
      				return;
      			}
      			//Building trees by dividing into two subtrees
      			buildTree(array, position*2,front,(front+end)/2);
      			buildTree(array, position*2+1,(front+end)/2+1,end);
  
      			recalc(position,front,end);
      		}
  
      		private void recalc(int position, int front, int end) {
      			sum[position]=(getSum(position*2,front,(front+end)/2)+getSum(position*2+1,(front+end)/2+1,end));
      			
      			if (sum[position] >= mod)
      				sum[position] -= mod;
      		}
  
  
      		private long getSum(int position,int front,int end){
      			return (sum[position]+lazy[position]*(long)(end-front+1))%mod;
      		}
  
      		public long querySum(int queryFront, int queryEnd) {
      			return querySum(1,0,size-1,queryFront,queryEnd);
      		}
  
      		private long querySum(int position,int front,int end, int queryFront, int queryEnd){
      			//Case for entirely inclusive
      			if(front>=queryFront&&queryEnd>=end){
      				return getSum(position,front,end);
      			}
      			//Case for entirely exclusive
      			if(end<queryFront||queryEnd<front){
      				return 0;
      			}
      			propagate(position,front,end);
      			long leftAns=querySum(position*2,front,(front+end)/2,queryFront,queryEnd);
      			long rightAns=querySum(position*2+1,(front+end)/2+1,end,queryFront,queryEnd);
      			if (leftAns+rightAns >= mod)
      				
      				return leftAns+rightAns-mod;
      			return leftAns+rightAns;
      		}
  
  
      		private void propagate(int position,int front, int end){
      			lazy[position*2]+=lazy[position];
      			
      			if (lazy[position*2] >= mod)
      				lazy[position*2] -= mod;
      			lazy[position*2+1]+=lazy[position];
      			
      			if (lazy[position*2+1] >= mod)
      				lazy[position*2+1] -= mod;
      			sum[position]=getSum(position,front,end);
      			lazy[position]=0;
      			//Set the propagation to 0 so that it will not propagate the value again and again
      		}
  
      		public void update(int updateFront, int updateEnd, long value){
      			update(1,0,size-1,updateFront,updateEnd,value);
      		}
  
      		private void update(int position, int front, int end, int updateFront,int updateEnd,long value){
      			//Case for entirely inclusive
      			if(front>=updateFront&&updateEnd>=end){
      				lazy[position]+=value;
      				if (lazy[position] >= mod)
          				lazy[position] -= mod;
      				return;
      			}
      			//Case for entirely exclusive
      			if(end<updateFront||updateEnd<front){
      				return;
      			}
      			propagate(position,front,end);
      			update(position*2,front,(front+end)/2,updateFront,updateEnd,value);
      			update(position*2+1,(front+end)/2+1,end,updateFront,updateEnd,value);
      			recalc(position,front,end);
      		}
      	}
      
  }
  
  //StringJoiner sj = new StringJoiner(" "); 
  //sj.add(strings)
  //sj.toString() gives string of those stuff w spaces or whatever that sequence is