Cho số nguyên dương \(n\) cùng hai dãy số nguyên dương \(l_1, l_2, \ldots, l_n\) và \(r_1, r_2, \ldots, r_n\). Bạn cần đếm số dãy số nguyên \((x_1, x_2, \ldots, x_n)\) sao cho:

• \(l_i \leq x_i \leq r_i\) với mọi \(1 \leq i \leq n\).
• \(lcm(x_1, x_2, \ldots, x_n) = \max(x_1, x_2, \ldots, x_n)\)

Ở đây, \(lcm(x_1, x_2, \ldots, x_n)\) là số nguyên dương \(X\) nhỏ nhất sao cho \(x_i\) là ước của \(X\) với mọi \(1 \leq i \leq n\); và \(\max(x_1, x_2, \ldots, x_n)\) là giá trị lớn nhất của dãy số này.

Do kết quả có thể rất lớn, bạn chỉ cần in ra kết quả theo modulo \(998244353\).

Input

Dòng đầu tiên chứa số nguyên \(\theta\) \((1 \leq \theta \leq 5)\) là số bộ dữ liệu. Tiếp theo là các bộ dữ liệu lần lượt được mô tả theo khuôn dạng sau:

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 100000)\).
• Trong \(n\) dòng còn lại, dòng thứ \(i\) chứa hai số nguyên \(l_i\) và \(r_i\) \((1 \leq l_i^{l_i} \leq r_i \leq 900000)\).

Output

• Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là số dãy số thỏa mãn các yêu cầu ở trên. Do kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số dãy đếm được khi chia cho \(998244353\).

Example

2
3
2 4
2 5
1 3
2
1 2
2 4

10
5