Різак дільників#13099
Вам задано колоду довжиною . Машина для розпилювання колод обробляє колоду, відрізаючи від неї шматок. Довжина відрізаного шматка точно дорівнює найбільшому власному дільнику довжини колоди (тобто найбільшому дільнику, строго меншому за саму довжину). Після цього машина викидає цей відрізаний шматок.
Щоб мінімізувати сумарну довжину змарнованої деревини, ви можете спочатку розпиляти колоду на кілька частин довжинами a_1, a_2, \dots, a_k таких, що \sum\limits_{i=1}^{k} a_i = n. Тоді машина оброблятиме кожну частину окремо.
Проте є нюанс: машина не може обробляти колоди довжиною . Якщо якась частина має довжину a_i = 1, машина зламається та викине усі колоди, які ви зібрали. Тому ви повинні забезпечити, щоб кожне a_i > 1.
Знайдіть мінімальну сумарну довжину колод, викинутих машиною.
Перший рядок містить одне ціле число (1 \le t \le 10^4) — кількість тестових випадків.
Єдиний рядок кожного тестового випадку містить одне ціле число (2 \le n \le 10^{9}) — початкову довжину колоди.
Для кожного тестового випадку виведіть одне ціле число — мінімальну сумарну довжину колод, викинутих машиною.
Приклад 1
Підзадача ( балів): (\sum n \le 100)
Підзадача ( балів): (\sum n \le 10^5)
Підзадача ( балів): Без додаткових обмежень.