题目描述 当 $N < k$ 时，$root(N, k) = N$；否则，$root(N, k) = root(N', k)$，其中 $N'$ 为 $N$ 的 $k$ 进制表示的各位数字之和。 给定 $x$, $y$, $k$，求 $root(x^y, k)$ 的值（$^$ 表示乘方，不是异或）。 其中 $2 \leq k \leq 16$，$0 < x, y < 2000000000$。 注意，有一半的测试点中 $x^y$ 会超出 $int$ 的范围（$\geq 2000000000$）。 输入格式 每组测试数据包括一行，包含三个整数 $x$ ($0 < x < 2000000000$)，$y$ ($0 < y < 2000000000$)，$k$ ($2 \leq k \leq 16$)。 输出格式 对于每一组数据，输出 $root(x^y, k)$ 的值。 输入样例 4 4 10 输出样例 4