题目描述

给定一个十进制自然数的范围和进制的范围，十进制自然数范围在1-44700 之间，进制的范围在2~36之间。给定范围里的数中，有些数的平方，在某进制下既是完全平方数又是回文数。本题的任务是统计给定范围内有多少个数的平方满足下列条件：仅在某一进制下既是完全平方数又是回文数。 说明：$3^2 = 9$，因为它在十进制和十一进制中都是回文数，所以9不能算；同样 $26^2 = 676$ 也不算。

输入输出格式

输入

一行四个整数 ，分别表示给定的十进制自然数的范围和进制的范围。

输出

一行一个正整数，表示给定范围内满足条件的数的个数。

样例

输入1

1 100 9 11

输出1

12

时间及空间限制

1s, 256MB.

说明/提示

课课通 P326-6 【样例说明】： 62= 36= 33 base 11 102= 100= 121 base9 11^2= 121= 121 base 10 122= 144= 121 base 11 202 = 400= 484 base 9 22^2= 484 = 484 base 10 24^2= 576= 484 base 11 72^2= 5184 = 3993 base 11 82^2= 6724= 10201 base 9 84^2= 7056 = 5335 base 11 91^2= 8281 = 12321 base 9 100^2= 10000 = 14641 base 9