题目描述

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

输入格式

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

输出格式

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

样例数据

input

1 100 9 11

output

12

样例说明

6^2=36=33 base 11

10^2=100=121 base 9

11^2=121=121 base 10

12^2=144=121 base 11

20^2=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

数据规模与约定

1<=n<=m<=10^5

1<=k<=t<=50;

时间限制：$1 \text{s}$

空间限制：$64 \text{MB}$