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.

2 3
1 1
2 2
1 2

2
2
1