В Берляндии год считается несчастливым, если его номер n можно записать как n = xa + yb, где a и b — целые неотрицательные числа.
Например, если x = 2 и y = 3, тогда годы 4 и 17 будут несчастливыми (4 = 20 + 31, 17 = 23 + 32 = 24 + 30), а год 18 не будет, так как не существует представления числа 18 в таком виде.
Отрезок лет называется Золотым Веком, если в нем нет ни одного несчастливого года.
Напишите программу, которая найдет максимальную длину Золотого Века, который начинается не раньше года l и заканчивается не позднее года r. Если все годы в отрезке [l, r] несчастливые, то ответ — 0.
Выходные данные
Выведите максимальную длину Золотого Века в промежутке [l, r].
Если все годы в отрезке [l, r] несчастливые, то выведите 0.
Примечание
В первом примере несчастливые годы — 2, 3, 4, 5, 7, 9 и 10. Максимальная длина Золотого Века достигается на отрезках [1, 1], [6, 6] и [8, 8].
Во втором примере длиннейший Золотой Век — отрезок [15, 22].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3 1 10
|
1
|
|
2
|
3 5 10 22
|
8
|
|
3
|
2 3 3 5
|
0
|