P13891 [蓝桥杯 2023 省 Python A] 子树的大小

给定一棵包含 $n$ 个结点的完全 $m$ 叉树，结点按从根到叶、从左到右的顺序依次编号。 例如下图是一个拥有 $11$ 个结点的完全 $3$ 叉树。 :::align{center}  :::align 你需要求出第 $k$ 个结点对应的子树拥有的结点数量。

输入包含多组询问。 输入的第一行包含一个整数 $T$，表示询问次数。 接下来 $T$ 行，每行包含三个整数 $n, m, k$，表示一组询问。

输出 $T$ 行，每行包含一个整数表示对应询问的答案。

**【评测用例规模与约定】** 对于 $40\%$ 的评测用例，$T \leq 50$，$n \leq 10^6$，$m \leq 16$； 对于所有评测用例，$1 \leq T \leq 10^5$，$1 \leq k \leq n \leq 10^9$，$2 \leq m \leq 10^9$。