Background

Heart beat to death.

Problem Description

Given a positive integer $n$. Write the lowest $n$ bits of every integer in $[0,2^n)$ in binary, from low to high, into a $2^n \times n$ matrix in order. Both dimensions of the matrix are indexed starting from $0$. For example, when $n=3$, the matrix looks like this:

Given $q$ queries. For each query, ask for the size of the 4-connected component containing the cell at index $(x,y)$ in this matrix, modulo $998244353$.

Input Format

The first line contains two positive integers $n, q$.

The next $q$ lines each contain two non-negative integers $x, y$, representing one query.

Output Format

Output $q$ lines, each containing one positive integer, which is the answer for each query modulo $998244353$.

2 2
1 1
2 0

3
1

Hint

Sample #1 Explanation

The figure shows the matrix when $n=2$, where cells with the same color form a 4-connected component.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $0\le y\lt n\le 10^{18}$, $0\le x\lt \min(2^n, 10^{18})$, $1\le q\le 5\times 10^5$.

Please use fast input/output methods.

Translated by ChatGPT 5