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 \leq x, y \leq 10^{18}, 1 \leq l \leq r \leq 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]~.