题目背景

要是什么都和 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$ 取模后的结果。

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

提示

【样例 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!)$
$14 \sim 17$	$\leq 10^6$
$18 \sim 25$	$\leq 10^{18}$		$10$

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^{18}$，$1 \leq k \leq \min(10^{18}, n!)$，$1 \leq q\le 10$。