题目描述

给出一个序列，长度为 $n$，其中每一项都是正整数。序列的第 $i$ 位 $a_i$ 属于区间 $[l_i,r_i]$。

求所有情况下 $\gcd(a_1,a_2,\dots,a_n)$ 的约数个数和，对 $998244353$ 取模。

输入格式

第一行一个正整数 $n$。$(1\le n\le 10^5)$

接下来 $n$ 行，第 $i$ 行两个正整数 $l_i,r_i$。$(1\le l_i\le r_i\le 3\times 10^5)$

输出格式

输出一行一个正整数，为所有情况下 $\gcd(a_1,a_2,\dots,a_n)$ 的约数个数和，对 $998244353$ 取模。

输入输出样例

样例输入 1

4
1 4
1 5
3 6
4 10

样例输出 1

598

样例输入 2

4
38943 94594
23 46566
29384 48372
1 3990

样例输出 2

173742882