Problem Background

If only everything were as simple as NPC problems.

Problem Description

Little A wants to write a love poem for Little B. He has come up with $n$ sentences, each with a beauty value of $1, 2, \dots, n$. Little A needs to arrange these sentences in a specific order to form a complete poem. In other words, Little A needs to rearrange these $n$ sentences into a permutation $p_1, p_2, \dots, p_n$ of $1 \sim n$; the beauty value of the $i$-th line of the poem is the beauty value of the original $p_i$-th sentence, which is $p_i$.

However, since Little A is an OIer, his literary talent is not very stable. He severely overestimates the beauty of his sentences. If a sentence has a beauty value of $x$ in Little A's eyes, then Little B perceives its beauty value as the position of the lowest bit of $1$ in the binary representation of $x$. Here, the lowest bit is considered position $1$, the next lowest is $2$, and so on. That is, the beauty value $f(x)$ in Little B's eyes is $1 + \log_2 \operatorname{lowbit}(x)$.

Little A knows that after Little B receives the poem, she will only read a segment of it, and the beauty value she feels is the sum of the beauty values of all the sentences she reads. Specifically, if the poem has $n$ sentences, Little B will randomly select an interval $[l, r]$ from all non-zero-length intervals in $[1, n]$, and feel the beauty value of $\displaystyle\sum_{l \leq i \leq r} f(p_i)$. To measure the beauty of a poem, Little A defines the total beauty value of a poem as the sum of the beauty values felt by Little B in all possible cases.

Ideally, the arrangement with the maximum total beauty value would be the best. Unfortunately, after meticulous calculations, Little A finds that he is most likely to succeed with Little B only when he chooses the poem with the total beauty value exactly as the $k$-th smallest. Therefore, Little A wants to know the $k$-th smallest possible total beauty value among the $n!$ essentially different poems. Two poems are considered essentially the same if and only if the original permutation $p_1, \dots, p_n$ is the same.

Little A realizes this is an NPC problem and turns to you for help. Since the total beauty value is too large, you only need to calculate the answer modulo $998244353$.

Additionally, Little A has written $q$ sets of poems, so you need to answer his $q$ questions separately.

Input Format

Read data from standard input.

The first line contains a positive integer $q$, representing the number of sets of poems.

For each set of data, there is a single line with two positive integers $n$ and $k$ describing Little A's question.

Output Format

Output to standard output.

For each set of poems, output a single line containing an integer, which is the $k$-th smallest total beauty value modulo $998244353$.

Sample Input and Output

Sample Input #1

2
3 2
3 6

Sample Output #1

13
14

Sample Input #2

5
4 1
4 10
4 16
4 20
4 24

Sample Output #2

32
34
36
36
38

Sample Input #3

10
1000000000000000000 1000000000000000000
1145141919810 19260817998244353
15 131413141314
36 93930322810121243
172 354354645654567654
666 233
1048576 2147483648
1000000007 1000000009
99824 44353
10 1

Sample Output #3

36226088
846277092
1096
12356
1239174
70731494
274614617
511280969
625722816
330

Notes

Sample 1 Explanation

For example, when $p = [1, 3, 2]$, the beauty values of each sentence in Little B's eyes are $[1, 1, 2]$. Then:

• When $l = 1$, $r = 1$, the sum of beauty values is $1$.
• When $l = 2$, $r = 2$, the sum of beauty values is $1$.
• When $l = 3$, $r = 3$, the sum of beauty values is $2$.
• When $l = 1$, $r = 2$, the sum of beauty values is $1 + 1 = 2$.
• When $l = 2$, $r = 3$, the sum of beauty values is $1 + 2 = 3$.
• When $l = 1$, $r = 3$, the sum of beauty values is $1 + 1 + 2 = 4$.

So the total beauty value of $p = [1, 3, 2]$ is $1 + 1 + 2 + 2 + 3 + 4 = 13$.

For all $3! = 6$ permutations $p$, their total beauty values sorted in ascending order are $13, 13, 13, 13, 14, 14$. Therefore, the answers for $k = 2$ and $k = 6$ are $13$ and $14$, respectively.

Data Range

The time limit for each test point varies. Specifically, the time limit for each point is $\max(q \times 0.5, 2)\ \rm{s}$.

For $100\%$ of the data, it is guaranteed that $1 \leq n \leq 10^{18}$, $1 \leq k \leq \min(10^{18}, n!)$, and $1 \leq q \leq 10$.

见题面 Input 部分

见题面 Output 部分