{"raw_statement":[{"iden":"background","content":"要是什么都和 NPC 问题一样简单就好了啊。"},{"iden":"statement","content":"小 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$。\n\n不过，由于小 A 是位 OIer，所以他的文采并不是很稳定。他实际上会严重高估自己诗句的优美程度。若一条诗句在小 A 眼里的优美度为 $x$，那么小 B 认为它的优美度是 **$x$ 在二进制表示下最低位的 $1$ 的位置**。其中，小 B 认为最低位的位置是 $1$，次低位为 $2$，以此类推。也就是说，小 B 眼中的优美度 $f(x)$ 为 $1 + \\log_2 \\operatorname{lowbit}(x)$。\n\n小 A 知道，小 B 拿到诗后，只会选取诗的一段来看，而她感受到的优美度是所有她读到的诗句之和。具体的，若诗有 $n$ 句，则小 B 会在 $[1, n]$ 的所有长度 $> 0$ 的区间中抽取一个 $[l, r]$，感受到 $\\displaystyle\\sum_{l \\leq i \\leq r}f(p_i)$ 的优美度。小 A 为了衡量一首诗的优美度，决定将一首诗的总优美度定义为 **所有情况下小 B 感受到的优美度之和**。\n\n照理来说，总优美度最大的组合方式必然是最好的。遗憾的是，在小 A 的精密计算下，他发现，只有他选择总优美度恰好为 **第 $k$ 小** 的情诗时，他才最有可能和小 B 走到一起。于是，小 A 想要知道，对于 $n!$ 首本质不同的诗，第 $k$ 小可能的总优美度是多少。两首诗本质相同当且仅当原排列 $p_1 \\dots p_n$ 相同。\n\n小 A 发现这是一个 NPC 问题，他只好来向你求助了。由于总优美度过于巨大，你只需要帮他求出答案对 $998244353$ 取模后的结果。\n\n特别的，小 A 写了 $q$ 组诗句，所以你需要分别回答他的 $q$ 个问题。"},{"iden":"input","content":"从标准输入中读入数据。\n\n第一行一个正整数 $q$，表示诗句的组数。\n\n对于每组数据，仅一行两个正整数 $n, k$ 描述小 A 的问题。"},{"iden":"output","content":"输出到标准输出。\n\n对于每组诗句，输出一行一个整数，表示第 $k$ 小的总优美度对 $998244353$ 取模后的结果。"},{"iden":"note","content":"#### 【样例 1 解释】\n\n例如，当 $p = [1, 3, 2]$ 时，小 B 眼中每句诗的优美度分别为 $[1, 1, 2]$。那么：\n\n- 当 $l = 1$，$r = 1$ 时，优美度之和为 $1$。\n- 当 $l = 2$，$r = 2$ 时，优美度之和为 $1$。\n- 当 $l = 3$，$r = 3$ 时，优美度之和为 $2$。\n- 当 $l = 1$，$r = 2$ 时，优美度之和为 $1 + 1 = 2$。\n- 当 $l = 2$，$r = 3$ 时，优美度之和为 $1 + 2 = 3$。\n- 当 $l = 1$，$r = 3$ 时，优美度之和为 $1 + 1 + 2 = 4$。\n\n所以 $p = [1, 3, 2]$ 的总优美度为 $1 + 1 + 2 + 2 + 3 + 4 = 13$。\n\n对于所有 $3! = 6$ 个排列 $p$，其总优美度从小到大排序后分别为 $13, 13, 13, 13, 14, 14$，因此当 $k = 2$ 与 $k = 6$ 时答案分别为 $13$ 和 $14$。\n\n---\n\n#### 【样例 2】\n\n见附件下的 $\\verb!npc/npc2.in!$ 与 $\\verb!npc/npc2.ans!$。\n\n---\n\n#### 【样例 3】\n\n见附件下的 $\\verb!npc/npc3.in!$ 与 $\\verb!npc/npc3.ans!$。\n\n---\n\n#### 【数据范围】\n\n**本题各测试点时间限制不相同。具体地，每个点的时间限制为 $\\max(q\\times 0.5, 2)\\ \\rm{s}$**。\n\n| 测试点编号 | $n$ | $k \\leq$ | $q = $ |\n| :--------: | :-: | :------: | :----: |\n| $1 \\sim 3$ | $\\leq 10$ | $n!$ | $2$ |\n| $4 \\sim 8$ | $\\leq 10^3$ | $2$ | $7$ |\n| $9 \\sim 13$ | $\\in [10^5, 10^6]$ | $\\min(10^{18}, n!)$ | $7$ |\n| $14 \\sim 17$ | $\\leq 10^6$ | $\\min(10^{18}, n!)$ | $7$ |\n| $18 \\sim 25$ | $\\leq 10^{18}$ | $\\min(10^{18}, n!)$ | $10$|\n\n对于 $100\\%$ 的数据，保证 $1 \\leq n \\leq 10^{18}$，$1 \\leq k \\leq \\min(10^{18}, n!)$，$1 \\leq q\\le 10$。"}],"translated_statement":null,"sample_group":[["2\n3 2\n3 6","13\n14\n"],["5\n4 1\n4 10\n4 16\n4 20\n4 24","32\n34\n36\n36\n38"],["10\n1000000000000000000 1000000000000000000\n1145141919810 19260817998244353\n15 131413141314\n36 93930322810121243\n172 354354645654567654\n666 233\n1048576 2147483648\n1000000007 1000000009\n99824 44353\n10 1","36226088\n846277092\n1096\n12356\n1239174\n70731494\n274614617\n511280969\n625722816\n330"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}