Два солдата играют в игру. Сначала один солдат выбирает целое положительное число n и называет его второму солдату. Затем второй солдат пытается совершить наибольшее количество ходов. На каждом ходу солдат выбирает положительное целое число x > 1, такое, что n делится на x, и заменяет число n числом n / x. Когда n становится равно 1 и больше нет возможных ходов, тогда игра завершается и счет второго солдата равен количеству совершённых им ходов.
Чтобы сделать игру поинтереснее, в качестве n солдат выбирает число вида a! / b! для некоторых положительных целых чисел a и b (a ≥ b). Здесь под k! имеется в виду факториал числа k, который определяется как произведение всех положительных целых чисел, не превосходящих k.
Определите максимально возможный счет второго солдата.
Выходные данные
Для каждой игры выведите максимальный счет, которого может достичь второй солдат.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 1
6 3
|
2
5
|