A - Pelea de Primos I

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Ocurre una catástrofe en Numberland, el número primo p esta celoso del número primo q. El cree que que hay mas números entre a y b inclusive que son divisibles por una mayor potencia de q que de p. Debemos ayudar a p a liberarse de este sentimiento. Sea a(n,x) el máximo k tal que n es divisible por x^k. Digamos que el numero n es p-dominante sobre q si a(n,p) > a(n,q). Encuentre cuantos numeros entre a y b inclusive son p-dominante sobre q.

Input

La primera y única linea de la entrada contiene a, b, p y q ;p 6= q; p y q son primos.
• En el subproblema I se cumple (1 ≤ a ≤ b ≤ 10^7);2 ≤ p,q ≤ 10^3
• En el subproblema II se cumple (1 ≤ a ≤ b ≤ 10^18);2 ≤ p,q ≤ 10^9

Output

Imprima un número - cuantos números n entre a y b inclusive son p-dominante sobre q.

Sample test(s)

Input
1 20 3 2
Output
4