Un año $desafortunado$ en Matelandia es aquel que su número $n$ puede ser representado como $n=x^a+y^b$, donde $a$ y $b$ son dos números enteros no negativos.

Por ejemplo, si $x=2$ y $y=3$ entonces los años 4 y 17 son $desafortunados$ $(4=2^0+3^1,17=2^3+3^2=2^4+3^0)$ y el año 18 no es $desafortunado$ dado que no existe dicha representación para él.

Un intervalo de años donde no hay años $desafortunados$ es llamado La Época Dorada.

Debes escribir un programa donde encuentres el largo máximo de La Época Dorada que comience no antes del año $l$ y termine no luego del año $r$. Si todos los años en el intervalo $[l,r]$ son $desafortunados$ entonces la respuesta es 0.

Entrada

La primera línea contiene cuatro enteros $x$, $y$, $l$ y $r$ $(2\le x,y\le {10}^{18},1\le l\le r\le {10}^{18})$.

Salida

Imprima el largo máximo de La Época Dorada dentro del rango $[l,r]$.

Si todos los años en el intervalo $[l,r]$ son $desafortunados$ imprime 0.

Ejemplo #1 de Entrada

2 3 1 10

Ejemplo #1 de Salida

1

Ejemplo #2 de Entrada

3 5 10 22

Ejemplo #2 de Salida

8

Explicación

En el primer caso de prueba los años $desafortunados$ son 2, 3, 4, 5, 7, 9, y, 10. Así que el máximo de La Época Dorada se alcanza en los intervalos $[1,1],[6,6]$ y $[8,8]$.

En el segundo caso de prueba el máximo de La Época Dorada es el intervalo $[15,22]$.