85. 子树的大小
内存限制：256 MB
时间限制：1.000 S
题目描述
给定一棵包含 n 个结点的完全 m 叉树，结点按从根到叶、从左到右的顺序依次编号。
例如下图是一个拥有 11 个结点的完全 3 叉树。
你需要求出第 k 个结点对应的子树拥有的结点数量。
输入
输入包含多组询问。
输入的第一行包含一个整数 T ，表示询问次数。
接下来 T 行，每行包含三个整数 n, m, k 表示一组询问。
输出
输出 T 行，每行包含一个整数表示对应询问的答案。
样例输入 复制
3
1 2 1
11 3 4
74 5 3样例输出 复制
1
2
24提示
对于 40% 的评测用例，T ≤ 50，n ≤ 106，m ≤ 16；
对于所有评测用例，1 ≤ T ≤ 105，1 ≤ k ≤ n ≤ 109，2 ≤ m ≤ 109。