Problem Description
ZY found a weird segment tree with range [1, n].
For one node a, b we choose a random integer x in range [a, b), seperate the segment into [a,x] and [x+1,b].
While doing query on this segment tree, bad thing happens. For one query [l, r]. If we want to obtain the information of the range [l, r], what is the expected number of nodes in the segment tree that would be visited?
For example, when querying range [2,4] in this segment tree, we will visit nodes in red.
Input
The first line contains two integer n,q.
The following q lines each contain a query interval [l,r].
1≤n,q≤106.
Output
For each query, output the expected number of visited nodes in a line, modulo 998244353.
Sample Input
2 3
1 1
2 2
1 2
Sample Output
2
2
1
