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 {
  	public static void main(String[] args) throws IOException 
  	{ 
  		FastScanner f= new FastScanner(); 
  		int ttt=1;
  //		ttt=f.nextInt();
  		PrintWriter out=new PrintWriter(System.out);
  		for(int tt=0;tt<ttt;tt++) {
  	        int N = f.nextInt();
  	        int M = f.nextInt();
  	        int MOD=998244353;
  	        int[] left = new int[N];
  	        int[] right = new int[N];
  	        for(int i=0; i < N; i++)
  	        {
  	            left[i] = f.nextInt();
  	            right[i] =f.nextInt();
  	        }
  	        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 = Math.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 = Math.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);
  		}
  		out.close();
  	} 
  	
  	static void sort(int[] p) {
          ArrayList<Integer> q = new ArrayList<>();
          for (int i: p) q.add( i);
          Collections.sort(q);
          for (int i = 0; i < p.length; i++) p[i] = q.get(i);
      }
  	static class FastScanner {
  		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st=new StringTokenizer("");
  		String next() {
  			while (!st.hasMoreTokens())
  				try {
  					st=new StringTokenizer(br.readLine());
  				} catch (IOException e) {
  					e.printStackTrace();
  				}
  			return st.nextToken();
  		}
  		
  		int nextInt() {
  			return Integer.parseInt(next());
  		}
  		int[] readArray(int n) {
  			int[] a=new int[n];
  			for (int i=0; i<n; i++) a[i]=nextInt();
  			return a;
  		}
  		long nextLong() {
  			return Long.parseLong(next());
  		}
  		double nextDouble() {
  			return Double.parseDouble(next());
  		}
  		long[] readLongArray(int n) {
  			long[] a=new long[n];
  			for (int i=0; i<n; i++) a[i]=nextLong();
  			return a;
  		}
  	}
  }