Given an n×n grid, there are q queries. Each query is of the form (x,y), where x≤y. Starting from cell (x,y), you can move from cell (i,j) to cells (i+1,k) and j≤k≤n. However, you cannot move to cells with coordinates (a,b) where a>b. Determine the number of ways to reach (n,n) from (x,y).
### Input
- The first line contains two integers n,q.
- The next q lines, each containing two integers x,y, representing a query.
### Output
- For each query, print an integer representing the number of paths modulo 998244353 from (x,y) to (n,n).
### Constraints
- 1≤n,q≤105.
- 1≤x≤y≤n.
### Sample test
Input
53241113
Output:
3149