问题描述

给定一棵包含 $n$ 个结点的完全 $m$ 叉树，结点按从根到叶、从左到右的顺序依次编号。例如下图是一个拥有 $11$ 个结点的完全 $3$ 叉树。

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

输入格式

输入包含多组询问。

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

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

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

1
2
24

对于 $40\%$ 的评测用例， $T≤50$ ， $n≤10^6$ ， $m≤16$ ；

对于所有评测用例， $1≤T≤10^5$ ， $1≤k≤n≤10^9$ ， $2≤m≤10^9$ 。