Bölen Kesici#13099
Size uzunluğu olan bir kütük veriliyor. Bir kütük kesme makinesi, kütükten bir parça keserek onu işler. Kesilen parçanın uzunluğu tam olarak kütüğün uzunluğunun en büyük öz bölenine eşittir (yani uzunluğun kendisinden kesinlikle küçük olan en büyük bölen). Makine daha sonra bu kesilen parçayı atar.
İsraf edilen odunun toplam uzunluğunu en aza indirmek için, kütüğü başlangıçta \sum\limits_{i=1}^{k} a_i = n olacak şekilde uzunlukları a_1, a_2, \dots, a_k olan birkaç parçaya bölebilirsiniz. Makine daha sonra her parçayı ayrı ayrı işleyecektir.
Ancak bir püf noktası var: makine uzunluğu olan kütükleri işleyemez. Herhangi bir parçanın uzunluğu a_i = 1 olursa, makine arızalanır ve topladığınız tüm kütükleri atar. Bu nedenle, her a_i > 1 olmasını sağlamalısınız.
Makinenin attığı kütüklerin minimum toplam uzunluğunu bulun.
İlk satır tek bir tam sayı (1 \le t \le 10^4) — test durumlarının sayısını içerir.
Her test durumunun tek satırı tek bir tam sayı (2 \le n \le 10^{9}) — kütüğün başlangıçtaki uzunluğunu içerir.
Her test durumu için tek bir tam sayı — makinenin attığı kütüklerin minimum toplam uzunluğunu yazdırın.
Örnek 1
Alt görev ( puan): (\sum n \le 100)
Alt görev ( puan): (\sum n \le 10^5)
Alt görev ( puan): Ek kısıt yoktur.