题目描述

$N<k$ 时，$root(N,k) = N$，否则，$root(N,k) = root(N',k)$。$N'$ 为 $N$ 的 $k$ 进制表示的各位数字之和。输入 $x,y,k$，输出 $root(x^y,k)$ 的值，$2=<k<=16$，$0<x,y<2000000000$，有一半的测试点里 $x^y$ 会溢出int的范围$(>=2000000000)$。

输入格式

每组测试数据包括一行，$x(0<x<2000000000)$，$y(0<y<2000000000)$，$k(2\leq k\leq 16)$。