write a go solution for 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,ldots,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].
- sumlimits_i=1^na_i<=m.
- gcd(a_1,a_2,ldots,a_n)=1.

Here, gcd(a_1,a_2,ldots,a_n) denotes the greatest common divisor (GCD) of integers a_1,a_2,ldots,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,ldots,a_n) and (b_1,b_2,ldots,b_n) are considered different if there exists i (1<=i<=n) such that a_ineb_i.

Input Format:
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 Format:
Print a single integer — the number of different mathematical states of this constellation, modulo 998,244,353.

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.. Output only the code with no comments, explanation, or additional text.