Segment

Problem Description

ZY found a weird segment tree with range [1, n]. For one node [a, b] (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 \leq n,q \leq 10^6$.

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

Source

2018 Multi-University Training Contest 2

https://acm.hdu.edu.cn/showproblem.php?pid=6317