질투하는 수

수의 나라에서 소수 $p$가 소수 $q$를 부러워한다. 두 소수의 우열을 가리기 위해, 주어진 구간 안에서 $p$가 $q$를 "이기는" 수가 몇 개인지 센다.

양의 정수 $n$과 소수 $x$에 대해, $x^k$이 $n$을 나누는 가장 큰 정수 $k$를 $\alpha(n, x)$로 정의한다. 즉 $\alpha(n, x)$는 $n$의 소인수분해에서 $x$의 지수이다.

$\alpha(n, p) > \alpha(n, q)$일 때 $n$을 $q$에 대해 $p$-우세($p$-dominating) 하다고 한다.

$a$, $b$, $p$, $q$가 주어질 때, $a \le n \le b$인 정수 $n$ 중에서 $q$에 대해 $p$-우세한 수가 몇 개인지 구하라.

첫 줄에 네 정수 $a$, $b$, $p$, $q$가 주어진다 ($1 \le a \le b \le 10^{18}$; $2 \le p, q \le 10^9$; $p \ne q$; $p$와 $q$는 모두 소수).

$[a, b]$ 안에서 $q$에 대해 $p$-우세한 정수 $n$의 개수를 정수 하나로 출력한다.

예시에서 $[1, 20]$ 안의 정수 중 $2$에 대해 $3$-우세한 수는 $3$, $9$, $15$, $18$이다.