CA喜欢玩数学。 数学课上老师提了个问题： “3位数中满足所包含数字不重复且为2的倍数的数有多少个？” CA很快就算出来了，然而，他在思考着另一个更难的题目： “在1到A^n中（$[1,A^n]$）满足所包含数字不重复（用A进制表示时）且为k的倍数的数有多少个？”
第一行t，表示有t组数据。 接下来t组数据，每组数据包含三个正整数A,n,k。（注意这里的A,n,k都是用十进制表示的） $1 \le T \le 20,~2 \le A \le 11,~0 \le n \le 10^9,~1 \le k \le 10^9$
对于每个数据，输出一行答案。
2 10 2 7 11 2 3
13 30
第一组数据中满足条件的数为 ${7,14,21,28,35,42,49,56,63,70,84,91,98}$ 共13个。