题目描述

给定一颗满 $K$ 叉树，深度为 $D$，即整棵树有 $1+K+K^2+\dots+K^D$ 个节点。

现在你可以选定若干条边并将其删除（也可以选择不删）。删除后将得到一个森林。求使森林中存在一棵树的节点数为 $X$ 的最小删除边数。

输入格式

第一行一个整数 $T$，表示有 $T$ 组数据。

接下来 $T$ 行，每行三个整数 $D,K,X$。中间用空格隔开。

输出格式

输出共 $T$ 行，每组数据输出一行。对于每组数据，输出最少要删除的边数。