题目描述

给定正整数 $l$，$r$，$k$，求有多少个整数 $x$ 满足 $l\le x\le r$ 且 $x^2\bmod k=\text{rev}(x)$。

其中 $a\bmod b$ 表示 $a$ 除以 $b$ 的余数，$\text{rev}(x)$ 表示 $x$ 数位反转得到的数，例如 $\text{rev}(3)=3$，$\text{rev}(234)=432$，$\text{rev}(380)=83$。

输入格式

输入一行三个正整数 $l,r,k$。

输出格式

输出一行一个整数表示答案。

样例输入

1 100 29

3

数据范围

对于 $40\%$ 的数据，$1\le l\le r\le 1000$，$1\le k\le 100$；// count2.in/ans

对于 $70\%$ 的数据，$1\le l\le r\le 10^6$，$1\le k\le 10^6$；// count3.in/ans

对于 $100\%$ 的数据，$1\le l\le r\le 10^9$，$1\le k\le 10^6$。// count4.in/ans