题目描述

给定一棵包含 $n$ 个结点的完全 $m$ 叉树，结点按从根到叶、从左到右的顺序依次编号。

例如下图是一个拥有 $11$ 个结点的完全 $3$ 叉树。

:::align{center} :::align

你需要求出第 $k$ 个结点对应的子树拥有的结点数量。

输入格式

输入包含多组询问。

输入的第一行包含一个整数 $T$，表示询问次数。

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

输出格式

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

3
1 2 1
11 3 4
74 5 3

1
2
24

提示

【评测用例规模与约定】

对于 $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$。