Cortadora de divisores#13099
Se te da un tronco de longitud . Una máquina cortadora de troncos procesa un tronco cortando un trozo de él. La longitud del trozo cortado es exactamente el máximo divisor propio de la longitud del tronco (es decir, el mayor divisor estrictamente menor que la propia longitud). Después, la máquina desecha ese trozo cortado.
Para minimizar la longitud total de la madera desperdiciada, puedes dividir inicialmente el tronco en varias partes de longitudes a_1, a_2, \dots, a_k tales que \sum\limits_{i=1}^{k} a_i = n. La máquina procesará entonces cada parte por separado.
Sin embargo, hay un detalle: la máquina no puede procesar troncos de longitud . Si alguna parte tiene longitud a_i = 1, la máquina se averiará y desechará todos los troncos que hayas reunido. Por lo tanto, debes asegurarte de que todo a_i > 1.
Encuentra la longitud total mínima de los troncos desechados por la máquina.
La primera línea contiene un único entero (1 \le t \le 10^4) — el número de casos de prueba.
La única línea de cada caso de prueba contiene un único entero (2 \le n \le 10^{9}) — la longitud inicial del tronco.
Para cada caso de prueba, imprime un único entero — la longitud total mínima de los troncos desechados por la máquina.
Ejemplo 1
Subtarea ( puntos): (\sum n \le 100)
Subtarea ( puntos): (\sum n \le 10^5)
Subtarea ( puntos): Sin restricciones adicionales.