The Poetic Permutation

Little A wants to write a love poem for Little B by arranging n sentences. Originally, the n sentences have beauty values 1, 2, …, n (each sentence x has beauty value x). Little A will rearrange these sentences into a permutation p₁, p₂, …, p_n, so that the ith line of the poem carries beauty p_i.

However, Little A overestimates his poetic talent. In his eyes a line’s beauty is x, but Little B judges its beauty as f(x)=1+\log_{2}(\mathrm{lowbit}(x)) in \(\LaTeX\) format, where \(\mathrm{lowbit}(x)\) denotes the value of the lowest set bit in the binary representation of x (its least‐significant 1 – the position of the LSB is counted starting from 1). For instance, if x=6 (binary 110) then \(\mathrm{lowbit}(6)=2\) and \(f(6)=1+\log_{2}2=2\).

After receiving the poem, Little B will only read a contiguous segment of lines. For a poem of n lines, every interval \([l,r]\) (with \(1\le l \le r \le n\)) is considered and Little B perceives its beauty as the sum \(\sum_{i=l}^{r} f(p_i)\). Little A defines the total beauty of a poem as the sum, over all contiguous intervals, of the perceived beauty.

Note that if we denote the weight of line i as \(w_i=i\times (n-i+1)\) (because line i appears in exactly \(i\cdot (n-i+1)\) contiguous segments), then the total beauty in terms of the permutation is:

[ T(p)=\sum_{i=1}^{n} w_i\cdot f(p_i). ]

Since there are n! different poems (two poems are different if their original permutation is different), Little A is curious: what is the total beauty of the poem that is the k^th smallest if all poems are sorted by total beauty (with multiplicities) ? Because the numbers can be huge, output the answer modulo 998244353.

You are given q queries. In each query you are given two integers n and k and you are to compute the desired total beauty modulo 998244353.

inputFormat

The input begins with an integer q (\(1 \le q\le Q\)) on a single line, denoting the number of queries. Each of the next q lines contains two integers n and k (n is the number of sentences; the value of k will be valid, i.e. \(1\le k\le \frac{n!}{\prod f_i!}\), where \(f_i\) are the frequencies of different values of \(f(x)\)).

It is guaranteed that n is small enough (for example, \(n \le 10\)) so that an algorithm using state space over bitmasks is feasible.

outputFormat

For each query, output one line containing the k^th smallest total beauty modulo 998244353.

sample

3
3 2
3 3
2 2

13
14
6