Bölən Kəsici#13099
Sizə uzunluğu olan bir kötük verilir. Kötük kəsən maşın kötüyü emal edərkən ondan bir parça kəsir. Kəsilən parçanın uzunluğu dəqiq olaraq kötüyün uzunluğunun ən böyük məxsusi böləninə bərabərdir (yəni uzunluğun özündən ciddi şəkildə kiçik olan ən böyük bölən). Sonra maşın bu kəsilmiş parçanı atır.
İsraf olunan odunun ümumi uzunluğunu minimuma endirmək üçün siz əvvəlcə kötüyü uzunluqları a_1, a_2, \dots, a_k olan bir neçə hissəyə bölə bilərsiniz, belə ki \sum\limits_{i=1}^{k} a_i = n. Maşın isə hər hissəni ayrıca emal edəcək.
Lakin bir incəlik var: maşın uzunluğu olan kötükləri emal edə bilmir. Əgər hər hansı hissənin uzunluğu a_i = 1 olarsa, maşın sıradan çıxacaq və topladığınız bütün kötükləri atacaq. Buna görə də hər bir a_i > 1 olmasını təmin etməlisiniz.
Maşının atdığı kötüklərin minimum ümumi uzunluğunu tapın.
Birinci sətirdə bir tam ədəd (1 \le t \le 10^4) — test hallarının sayı verilir.
Hər test halının yeganə sətrində bir tam ədəd (2 \le n \le 10^{9}) — kötüyün ilkin uzunluğu verilir.
Hər test halı üçün bir tam ədəd — maşının atdığı kötüklərin minimum ümumi uzunluğunu çap edin.
Nümunə 1
Altməsələ ( bal): (\sum n \le 100)
Altməsələ ( bal): (\sum n \le 10^5)
Altməsələ ( bal): Əlavə məhdudiyyət yoxdur.