В Берляндии год считается несчастливым, если его номер n можно записать как n = x^a + y^b, где a и b — целые неотрицательные числа.

Например, если x = 2 и y = 3, тогда годы 4 и 17 будут несчастливыми (4 = 2⁰ + 3¹, 17 = 2³ + 3² = 2⁴ + 3⁰), а год 18 не будет, так как не существует представления числа 18 в таком виде.

Отрезок лет называется Золотым Веком, если в нем нет ни одного несчастливого года.

Напишите программу, которая найдет максимальную длину Золотого Века, который начинается не раньше года l и заканчивается не позднее года r. Если все годы в отрезке [l, r] несчастливые, то ответ — 0.