1787B - Number Factorization - CodeForces Solution

//───────────────────────────────────────────────────────────────────────────────────────────────────────
//─────────██████─██████████████─██████──────────██████─████████──████████─██████████████─██████████████─
//─────────██░░██─██░░░░░░░░░░██─██░░██████████████░░██─██░░░░██──██░░░░██─██░░░░░░░░░░██─██░░░░░░░░░░██─
//─────────██░░██─██░░██████████─██░░░░░░░░░░░░░░░░░░██─████░░██──██░░████─██████████░░██─██░░██████████─
//─────────██░░██─██░░██─────────██░░██████░░██████░░██───██░░░░██░░░░██───────────██░░██─██░░██─────────
//─────────██░░██─██░░██████████─██░░██──██░░██──██░░██───████░░░░░░████───██████████░░██─██░░██████████─
//─────────██░░██─██░░░░░░░░░░██─██░░██──██░░██──██░░██─────████░░████─────██░░░░░░░░░░██─██░░░░░░░░░░██─
//─██████──██░░██─██░░██████████─██░░██──██████──██░░██───────██░░██───────██░░██████████─██████████░░██─
//─██░░██──██░░██─██░░██─────────██░░██──────────██░░██───────██░░██───────██░░██─────────────────██░░██─
//─██░░██████░░██─██░░██████████─██░░██──────────██░░██───────██░░██───────██░░██████████─██████████░░██─
//─██░░░░░░░░░░██─██░░░░░░░░░░██─██░░██──────────██░░██───────██░░██───────██░░░░░░░░░░██─██░░░░░░░░░░██─
//─██████████████─██████████████─██████──────────██████───────██████───────██████████████─██████████████─
//───────────────────────────────────────────────────────────────────────────────────────────────────────
#include <iostream>
#include <bits/stdc++.h>
//======================================================
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//======================================================
#define input(v) for(auto&it:v){cin>>it;}
#define output(v) for(auto&it:v){cout<<it<<" ";}cout<<"\n"
//======================================================
const int N = 1e6+5;
const int MOD = 1e9+7;
const double pi= 3.1415926535897932;
//======================================================
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
//======================================================
void File(){
    freopen("text.in","r",stdin);
    //    freopen("output.txt","w",stdout);
}
//======================================================
void FastCode(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
//======================================================
struct FenwickTree{
    vector<ll> arr;
    int n;
    FenwickTree(int N){
        n=N;
        arr.resize(N+5);
    }
    void update(ll idx , ll val){
        while(idx < n+5){
            arr[idx]+=val;
            idx += idx&-idx;
        }
    }
    ll sum(ll idx){
        ll s=0;
        while(idx){
            s+=arr[idx];
            idx -= idx&-idx;
        }
        return s;
    }
    ll sum(ll l , ll r){
        return sum(r)-sum(l-1);
    }
    ll get(int idx){
        return sum(idx)-sum(idx-1);
    }
};
//======================================================
ll gcd(ll a , ll b){
    if(min(a,b) == 0) return max(a,b);
    else return gcd(b , a%b);
}
//======================================================
ll lcm(ll a , ll b){
    return a / gcd(a,b) * b;
}
//======================================================
ll KadaneMaxSum(vector<ll> &arr){
    ll globalSum = arr[0];
    ll curSum = arr[0];
    int n = arr.size();
    for(int i = 1 ; i < n ; i++){
        curSum = max(arr[i] ,curSum+arr[i]);
        globalSum = max(globalSum , curSum);
    }
    return globalSum;
}
//======================================================
ll KadaneMinSum(vector<ll> &arr){
    ll globalSum = arr[0];
    ll curSum = arr[0];
    int n = arr.size();
    for(int i = 1 ; i < n ; i++){
        curSum = min(arr[i] ,curSum+arr[i]);
        globalSum = min(globalSum , curSum);
    }
    return globalSum;
}
//======================================================
struct Sieve{
public:
    vector<int> primes;
    Sieve(int n){
        N = n;
        isPrime.resize(N+5);
        for(int i = 0 ; i < N+5 ; i++)
            isPrime[i] = true;
        sieve();
    }
    bool check(int x){
        return isPrime[x];
    }
    void sieve(){
        isPrime[0] = isPrime[1] = false;
        for(int i = 2 ; i*i < N ; i++){
            if(isPrime[i])
                for(int j = i*i ; j< N ; j+=i){
                    isPrime[j] = false;
                }

        }
        for(int i = 2 ; i < N ; i++)
            if(isPrime[i])
                primes.push_back(i);
    }
private:
    vector<int> isPrime;
    int N;
};
ll stringMod(string num , ll mod){
    ll ans = 0;
    int n = num.size();
    for(int i = 0 ; i < n ; i++){
        int d = num[i]-'0';
        ans = (ans*10+d)%mod;
    }
    return ans;
}
//======================================================
ll fp(ll base , ll pow , int cMod = MOD){
    ll ans = 1;
    while(pow){
        if(pow&1) ans = (ans%cMod * base%cMod)%cMod;
        base = (base*base)%cMod;
        pow >>=1;
    }
    return ans;
}
//======================================================
bool isPrime(ll n) {
    if (n == 2) return true;
    if (n < 2 || n % 2 == 0) return false;
    for (ll i = 3; i * i <= n; i += 2)
        if (n % i == 0)  return false;
    return true;
}
//======================================================
ll findXOR(ll n){
    ll mod = n % 4;
    if (mod == 0)
        return n;
    else if (mod == 1)
        return 1;
    else if (mod == 2)
        return n + 1;
    else if (mod == 3)
        return 0;
}
ll findXOR(ll l, ll r){
    return (findXOR(l - 1) ^ findXOR(r));
}

//======================================================
void testCase(int ct) {
    int n;
    cin>>n;
    int arr[30];
    for (int i = 0; i < 30; ++i)
        arr[i]=1;
    for (int i = 2; i*i <= n; ++i) {
        int c=0;
        while(n%i==0){
            arr[c]*=i;
            n/=i;
            c++;
        }
    }
    if(n!=1)
        arr[0]*=n;
    int mx=0;
    for (int i = 0; i < 30; ++i) {
        if(arr[i]!=1)
            mx+=arr[i];
    }
    cout<<mx<<'\n';

}
int main(){
    //File();
    FastCode();
    int t=1;
    cin>>t;
    for(int i = 1 ; i <= t ; i++)
        testCase(i);
    return 0;
}