Ibti раздумывал о хорошем названии для этой задачи, которое подойдёт к теме раунда (число три). Он сразу подумал о третьей производной, но это было довольно глупо, поэтому он решил включить лучшую группу в мире — Three Days Grace.
Вам дано мультимножество \(A\) изначального размера \(n\), элементы которого — целые числа от \(1\) до \(m\). За одну операцию можно сделать следующее:
- выбрать значение \(x\) из мультимножества \(A\), затем
- выбрать два целых числа \(p\) и \(q\) такие, что \(p, q > 1\) и \(p \cdot q = x\). Добавить \(p\) и \(q\) в \(A\), удалить \(x\) из \(A\).
Заметьте, что размер мультимножества \(A\) увеличивается на \(1\) после каждой операции.
Назовём балансом мультимножества \(A\) значение \(\max(a_i) - \min(a_i)\). Найдите минимально возможный баланс после применения нескольких (возможно, нуля) операций.
Примечание
В первом наборе входных данных мы можем применить операцию к каждому из чисел \(4\) с \((p,q) = (2,2)\) и сделать мультимножество \(\{2,2,2,2,2,2,2\}\) с балансом \(\max(\{2,2,2,2,2,2,2\}) - \min(\{2,2,2,2,2,2,2\}) = 0\). Очевидно, мы не можем сделать баланс меньше \(0\).
Во втором входных данных мы можем применить операция к \(12\) с \((p,q) = (3,4)\). После этого мультимножество станет равным \(\{3,4,2,3\}\). Мы можем применить ещё одну операцию к числу \(4\) с \((p,q) = (2,2)\), сделав мультимножество \(\{3,2,2,2,3\}\) с балансом \(1\).
В третьем входных данных мы можем применить операцию к \(35\) с \((p,q) = (5,7)\). Итоговое мультимножество будет \(\{6,5,7\}\) с балансом \(7-5 = 2\).
В четвёртом наборе входных данных мы не может применить никакую операцию, поэтому ответ равен \(5 - 1 = 4\).