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.util.*;
  import java.util.Map.Entry;
  
  import java.math.*;
  import java.io.*;
  
  public class Main {
  	static final long mod = 998244353;
  
  	public static void main(String[] args) throws FileNotFoundException {
  		InputReader in = new InputReader(System.in);
  		// Scanner in = new Scanner(System.in);
  		// Scanner in = new Scanner(new BufferedReader(new
  		// InputStreamReader(System.in)));
  		PrintWriter out = new PrintWriter(System.out);
  		// InputReader in = new InputReader(new
  		// File("ethan_traverses_a_tree.txt"));
  		// PrintWriter out = new PrintWriter(new
  		// File("ethan_traverses_a_tree-output.txt"));
  
  		int n = in.nextInt();
  		int m = in.nextInt();
  		int[][] a = new int[n][2];
  		for (int i = 0; i < n; i++) {
  			a[i][0] = in.nextInt();
  			a[i][1] = in.nextInt();
  		}
  
  		long[] dp = new long[m + 1];
  		long countgt1 = 0;
  		for (int i = m / n; i >= 2; i--) {
  			long nowcount = getcount(a, n, m, i);
  			for (int j = 2; j * i <= m / n; j++) {
  				nowcount = (nowcount - dp[j * i] + mod) % mod;
  			}
  
  			dp[i] = nowcount;
  			countgt1 = (countgt1 + nowcount) % mod;
  		}
  
  		long ans = (getcount(a, n, m, 1) - countgt1 + mod) % mod;
  		out.printf("%d\n", ans);
  
  		out.close();
  	}
  
  	public static long getcount(int[][] tmpa, int n, int m, int divisor) {
  		int[][] a = new int[n][2];
  
  		for (int i = 0; i < n; i++) {
  			if (tmpa[i][0] % divisor == 0) {
  				a[i][0] = tmpa[i][0] / divisor;
  			} else {
  				a[i][0] = tmpa[i][0] / divisor + 1;
  			}
  
  			a[i][1] = tmpa[i][1] / divisor;
  			if (a[i][1] < a[i][0]) {
  				return 0;
  			}
  		}
  
  		int m2 = m / divisor;
  		long[][] dp = new long[n][m2 + 1];
  		long[][] sum = new long[n][m2 + 1];
  		for (int i = 0; i < n; i++) {
  			for (int j = 0; j <= m2; j++) {
  				if (i == 0) {
  					if (j >= a[i][0] && j <= a[i][1]) {
  						dp[i][j] = 1;
  					} else {
  						dp[i][j] = 0;
  					}
  				} else {
  					int prestart = j - a[i][1];
  					int preend = j - a[i][0];
  
  					if (preend < 0) {
  						dp[i][j] = 0;
  					} else {
  						if (prestart <= 0) {
  							dp[i][j] = sum[i - 1][preend];
  						} else {
  							dp[i][j] = (sum[i - 1][preend] - sum[i - 1][prestart - 1] + mod) % mod;
  						}
  					}
  				}
  
  				if (j == 0) {
  					sum[i][j] = dp[i][j];
  				} else {
  					sum[i][j] = (sum[i][j - 1] + dp[i][j]) % mod;
  				}
  			}
  		}
  
  		return sum[n - 1][m2];
  	}
  
  	static class InputReader {
  		BufferedReader br;
  		StringTokenizer st;
  
  		public InputReader(File f) {
  			try {
  				br = new BufferedReader(new FileReader(f));
  			} catch (FileNotFoundException e) {
  				e.printStackTrace();
  			}
  		}
  
  		public InputReader(InputStream in) {
  			br = new BufferedReader(new InputStreamReader(in));
  		}
  
  		public String next() {
  			while (st == null || !st.hasMoreTokens()) {
  				try {
  					st = new StringTokenizer(br.readLine());
  				} catch (IOException e) {
  					e.printStackTrace();
  				}
  			}
  			return st.nextToken();
  		}
  
  		public boolean hasNext() {
  			while (st == null || !st.hasMoreTokens()) {
  				String s = null;
  				try {
  					s = br.readLine();
  				} catch (IOException e) {
  					e.printStackTrace();
  				}
  				if (s == null)
  					return false;
  				st = new StringTokenizer(s);
  			}
  			return true;
  		}
  
  		public int nextInt() {
  			return Integer.parseInt(next());
  		}
  
  		public long nextLong() {
  			return Long.parseLong(next());
  		}
  
  		public double nextDouble() {
  			return Double.parseDouble(next());
  		}
  	}
  }