#P1451. 地下墓穴探險
-
ID: 1451
Type: Default
1000ms
64MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> 地下墓穴探險
題目描述
你和一位魔法師朋友在一個地下墓穴探險的時候突然被一堆的怪獸包圍，封住了出口。為了可以回到地面，你們必須把所有的怪獸都消滅掉，可是只有用魔法可以消滅那些怪獸。每一隻怪獸身上都有一個整數，代表要消滅它所需要的法力值，然而，你的魔法師朋友法力有限。身為一位劍士的你，決定去幫一下你的朋友。
雖然你不能直接消滅怪獸，但是你知道你可以把怪獸劈開。每劈一下怪獸就會分成三隻小怪獸，每一隻小怪獸上的數值乘起來會是等於原本未被劈開的怪獸的數值，而這個分成那三個數是可以由你的精準劍法來決定的。注意小怪獸不能再被劈開。
現在有 T 隻怪獸，對於每一隻怪獸都有一個整數 n ，代表該怪獸上的數值。保證每一個 n 都能夠寫成至少三個非1的數的積。
請問你的魔法師朋友最少要用多少法力來消滅所有的怪獸？
輸入格式
第一行有一個正整數 T ，代表有 T 個數
接下來 T 行，每行有一個正整數 n
輸出格式
一個數，為魔法師所需要的最少法力
Samples
3
174
918
114
90
提示
174 = 2 x 3 x 29
918 = 6 x 9 x 17
114 = 2 x 3 x 19
2 + 3 + 29 + 6 + 9 + 17 + 2 + 3 + 19 = 90
1 ≤ T ≤ 100
1 ≤ n ≤ 1e9
1 ≤ n ≤ 1e9
原始資料
- Zero1 題號：
b452 - Hydro 題號：
Z1452 - Locale：
en_US - Display：
open