Черепаха и Свинка играют в числовую игру.
Сначала Черепаха выберет целое число \(x\), такое что \(l \le x \le r\), где \(l, r\) заданы. Также гарантируется, что \(2l \le r\).
Затем Свинка будет выполнять следующую операцию, пока \(x\) не станет равным \(1\):
- Выберите целое число \(p\) такое, что \(p \ge 2\) и \(p \mid x\) (т.е. \(x\) делится на \(p\)).
- Замените \(x\) на \(\frac{x}{p}\), и увеличьте счет на \(1\).
Счет изначально равен \(0\). И Черепаха, и Свинка хотят максимизировать счет. Пожалуйста, помогите им вычислить максимальный счет.
Выходные данные
Для каждого теста выведите одно целое число — максимальный счет.
Примечание
В первом тесте Черепаха может выбрать целое число \(x\), такое что \(2 \le x \le 4\). Она может выбрать \(x = 4\). Затем Свинка может \(2\) раза выбрать \(p = 2\). После этого \(x\) станет равным \(1\), и счет будет равен \(2\), что является максимальным ответом для этого теста.
Во втором тесте Черепаха может выбрать целое число \(3 \le x \le 6\). Она может выбрать \(x = 6\). Затем Свинка может выбрать \(p = 2\), затем выбрать \(p = 3\). После этого \(x\) станет равным \(1\), и счет будет равен \(2\), что является максимальным ответом для этого теста.
В третьем тесте Черепаха может выбрать \(x = 12\).
В четвертом тесте Черепаха может выбрать \(x = 16\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 4
3 6
2 15
6 22
114514 1919810
|
2
2
3
4
20
|