2096: [蓝桥杯2023初赛] 子树的大小
内存限制：512 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：116
通过：51
题目描述
给定一棵包含 n 个结点的完全 m 叉树，结点按从根到叶、从左到右的顺序依次编号。
例如下图是一个拥有 11 个结点的完全 3 叉树。
你需要求出第 k 个结点对应的子树拥有的结点数量。
例如下图是一个拥有 11 个结点的完全 3 叉树。
你需要求出第 k 个结点对应的子树拥有的结点数量。
输入格式
输入包含多组询问。
输入的第一行包含一个整数 T ，表示询问次数。
接下来 T 行，每行包含三个整数 n, m, k 表示一组询问。
对于 40% 的评测用例，T ≤ 50，n ≤ 106，m ≤ 16 ；
对于 100% 的评测用例，1 ≤ T ≤ 105，1 ≤ k ≤ n ≤ 109，2 ≤ m ≤ 109 。
输入的第一行包含一个整数 T ，表示询问次数。
接下来 T 行，每行包含三个整数 n, m, k 表示一组询问。
对于 40% 的评测用例，T ≤ 50，n ≤ 106，m ≤ 16 ；
对于 100% 的评测用例，1 ≤ T ≤ 105，1 ≤ k ≤ n ≤ 109，2 ≤ m ≤ 109 。
输出格式
输出 T 行，每行包含一个整数表示对应询问的答案。
输入样例 复制
3
1 2 1
11 3 4
74 5 3输出样例 复制
12
24