A129377.皓仔的进制回文数

皓仔最近在学习进制转换和回文串。

对于一个正整数，如果把它转换成 $x$ 进制后，得到的表示从左往右读和从右往左读完全相同，那么皓仔就称这个数是一个“$x$ 进制回文数”。

例如：

• $9$ 转换成 $2$ 进制是 1001，是回文串；
• $10$ 转换成 $2$ 进制是 1010，不是回文串；
• $15$ 转换成 $16$ 进制是 F，是回文串。

现在给定三个整数 $l,r,x$，请你统计在 $l$ 到 $r$ 范围内，有多少个整数转换成 $x$ 进制后是回文串。

其中，区间包含左右端点，也就是统计 $[l,r]$ 中满足条件的整数个数。

输入一行，包含三个整数 $l,r,x$。

输出一个整数，表示区间 $[l,r]$ 中 $x$ 进制回文数的个数。

【数据范围】

对于所有测试数据保证：

• $1 \le l \le r \le 10^6$
• $2 \le x \le 16$