挑战 NPC IV

题目背景

要是什么都和 NPC 问题一样简单就好了啊。

题目描述

小 A 想为小 B 写一首情诗。他现在想出了 $n$ 个句子,每个句子的优美度分别为 $1, 2 \dots n$。小 A 需要按照一定的顺序将他们组合起来,拼成一首完整的诗。换句话说,小 A 需要重新排列这 $n$ 个句子,形成一个 $1 \sim n$ 的排列 $p_1, p_2\dots p_n$;第 $i$ 行诗句的优美度就是原先第 $p_i$ 个句子的优美度,也就是 $p_i$。 不过,由于小 A 是位 OIer,所以他的文采并不是很稳定。他实际上会严重高估自己诗句的优美程度。若一条诗句在小 A 眼里的优美度为 $x$,那么小 B 认为它的优美度是 **$x$ 在二进制表示下最低位的 $1$ 的位置**。其中,小 B 认为最低位的位置是 $1$,次低位为 $2$,以此类推。也就是说,小 B 眼中的优美度 $f(x)$ 为 $1 + \log_2 \operatorname{lowbit}(x)$。 小 A 知道,小 B 拿到诗后,只会选取诗的一段来看,而她感受到的优美度是所有她读到的诗句之和。具体的,若诗有 $n$ 句,则小 B 会在 $[1, n]$ 的所有长度 $> 0$ 的区间中抽取一个 $[l, r]$,感受到 $\displaystyle\sum_{l \leq i \leq r}f(p_i)$ 的优美度。小 A 为了衡量一首诗的优美度,决定将一首诗的总优美度定义为 **所有情况下小 B 感受到的优美度之和**。 照理来说,总优美度最大的组合方式必然是最好的。遗憾的是,在小 A 的精密计算下,他发现,只有他选择总优美度恰好为 **第 $k$ 小** 的情诗时,他才最有可能和小 B 走到一起。于是,小 A 想要知道,对于 $n!$ 首本质不同的诗,第 $k$ 小可能的总优美度是多少。两首诗本质相同当且仅当原排列 $p_1 \dots p_n$ 相同。 小 A 发现这是一个 NPC 问题,他只好来向你求助了。由于总优美度过于巨大,你只需要帮他求出答案对 $998244353$ 取模后的结果。 特别的,小 A 写了 $q$ 组诗句,所以你需要分别回答他的 $q$ 个问题。

输入输出格式

输入格式


从标准输入中读入数据。 第一行一个正整数 $q$,表示诗句的组数。 对于每组数据,仅一行两个正整数 $n, k$ 描述小 A 的问题。

输出格式


输出到标准输出。 对于每组诗句,输出一行一个整数,表示第 $k$ 小的总优美度对 $998244353$ 取模后的结果。

输入输出样例

输入样例 #1

2
3 2
3 6

输出样例 #1

13
14

输入样例 #2

5
4 1
4 10
4 16
4 20
4 24

输出样例 #2

32
34
36
36
38

输入样例 #3

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

输出样例 #3

36226088
846277092
1096
12356
1239174
70731494
274614617
511280969
625722816
330

说明

#### 【样例 1 解释】 例如,当 $p = [1, 3, 2]$ 时,小 B 眼中每句诗的优美度分别为 $[1, 1, 2]$。那么: - 当 $l = 1$,$r = 1$ 时,优美度之和为 $1$。 - 当 $l = 2$,$r = 2$ 时,优美度之和为 $1$。 - 当 $l = 3$,$r = 3$ 时,优美度之和为 $2$。 - 当 $l = 1$,$r = 2$ 时,优美度之和为 $1 + 1 = 2$。 - 当 $l = 2$,$r = 3$ 时,优美度之和为 $1 + 2 = 3$。 - 当 $l = 1$,$r = 3$ 时,优美度之和为 $1 + 1 + 2 = 4$。 所以 $p = [1, 3, 2]$ 的总优美度为 $1 + 1 + 2 + 2 + 3 + 4 = 13$。 对于所有 $3! = 6$ 个排列 $p$,其总优美度从小到大排序后分别为 $13, 13, 13, 13, 14, 14$,因此当 $k = 2$ 与 $k = 6$ 时答案分别为 $13$ 和 $14$。 --- #### 【样例 2】 见附件下的 $\verb!npc/npc2.in!$ 与 $\verb!npc/npc2.ans!$。 --- #### 【样例 3】 见附件下的 $\verb!npc/npc3.in!$ 与 $\verb!npc/npc3.ans!$。 --- #### 【数据范围】 **本题各测试点时间限制不相同。具体地,每个点的时间限制为 $\max(q\times 0.5, 2)\ \rm{s}$**。 | 测试点编号 | $n$ | $k \leq$ | $q = $ | | :--------: | :-: | :------: | :----: | | $1 \sim 3$ | $\leq 10$ | $n!$ | $2$ | | $4 \sim 8$ | $\leq 10^3$ | $2$ | $7$ | | $9 \sim 13$ | $\in [10^5, 10^6]$ | $\min(10^{18}, n!)$ | $7$ | | $14 \sim 17$ | $\leq 10^6$ | $\min(10^{18}, n!)$ | $7$ | | $18 \sim 25$ | $\leq 10^{18}$ | $\min(10^{18}, n!)$ | $10$| 对于 $100\%$ 的数据,保证 $1 \leq n \leq 10^{18}$,$1 \leq k \leq \min(10^{18}, n!)$,$1 \leq q\le 10$。