题目描述

给定整数范围 $[L,R]$ 和进制范围 $[A,B]$。对每个整数 $x$，考察 $x^2$ 在进制 $A,A+1,\ldots,B$ 中的表示。如果恰好只有一种进制的表示是回文串，则这个 $x$ 满足要求。统计满足要求的整数个数。

输入格式

一行四个整数 $L,R,A,B$。

输出格式

输出满足要求的整数个数。

样例

1 100 9 11

12

数据范围

$1\le L\le R\le44700$，$2\le A\le B\le36$。