Background

If only everything were as easy as an NPC problem.

Problem Description

Little A wants to write a love poem for Little B. He has come up with $n$ sentences, and the elegance of each sentence is $1, 2 \dots n$, respectively. Little A needs to combine them in some order to form a complete poem. In other words, Little A needs to reorder these $n$ sentences to form a permutation $p_1, p_2\dots p_n$ of $1 \sim n$; the elegance of the $i$-th line is the elegance of the original $p_i$-th sentence, that is, $p_i$.

However, since Little A is an OIer, his writing quality is not very stable. In fact, he will greatly overestimate how elegant his sentences are. If a sentence has elegance $x$ in Little A's eyes, then Little B thinks its elegance is the position of the lowest $1$ bit in the binary representation of $x$. Here, Little B considers the lowest bit position to be $1$, the next lowest to be $2$, and so on. That is, the elegance in Little B's eyes is $f(x) = 1 + \log_2 \operatorname{lowbit}(x)$.

Little A knows that after Little B gets the poem, she will only choose a segment of it to read, and the elegance she feels is the sum of the lines she reads. Specifically, if the poem has $n$ lines, then Little B will pick an interval $[l, r]$ among all intervals in $[1, n]$ with length $> 0$, and feel an elegance of $\displaystyle\sum_{l \leq i \leq r}f(p_i)$. To measure a poem's elegance, Little A defines the poem's total elegance as the sum of the elegance Little B feels in all cases.

In principle, the arrangement with the maximum total elegance must be the best. Unfortunately, after Little A's precise calculations, he found that only when he chooses the love poem whose total elegance is exactly the $k$-th smallest will he be most likely to end up with Little B. So Little A wants to know: among the $n!$ essentially different poems, what is the possible total elegance of the $k$-th smallest one. Two poems are essentially the same if and only if the original permutation $p_1 \dots p_n$ is the same.

Little A discovered that this is an NPC problem, so he had to ask you for help. Since the total elegance is too large, you only need to output the answer modulo $998244353$.

In particular, Little A wrote $q$ groups of sentences, so you need to answer his $q$ queries separately.

Input Format

Read from standard input.

The first line contains a positive integer $q$, representing the number of groups of sentences.

For each group of testdata, there is only one line containing two positive integers $n, k$ describing Little A's query.

Output Format

Write to standard output.

For each group of sentences, output one integer per line, representing the total elegance of the $k$-th smallest poem modulo $998244353$.

2
3 2
3 6

13
14

5
4 1
4 10
4 16
4 20
4 24

32
34
36
36
38

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

36226088
846277092
1096
12356
1239174
70731494
274614617
511280969
625722816
330

Hint

Sample 1 Explanation

For example, when $p = [1, 3, 2]$, the elegance of each line in Little B's eyes is $[1, 1, 2]$. Then:

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

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

For all $3! = 6$ permutations $p$, sorting their total elegance from small to large gives $13, 13, 13, 13, 14, 14$. Therefore, when $k = 2$ and $k = 6$, the answers are $13$ and $14$, respectively.

Sample 2

See the attached $\verb!npc/npc2.in!$ and $\verb!npc/npc2.ans!$.

Sample 3

See the attached $\verb!npc/npc3.in!$ and $\verb!npc/npc3.ans!$.

Constraints

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

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

Translated by ChatGPT 5