#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define ms1(dp) memset(dp, -1, sizeof(dp));
#define ms0(dp) memset(dp, 0, sizeof(dp));
#define minheap int, vector<int>, greater<int>
#define setbits(x) __builtin_popcountll(x) //count number of 1
#define zrobits(x) __builitin_ctzll(x) //count number of zero before 1st 1 ex- (110000)2 ->4
#define MOD 1000000007
#define INF 1e18
#define ps(x, y) fixed << setprecision(y) << x
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define ALL(x) x.begin(), x.end()
#define w(x) \
int x; \
cin >> x; \
while (x--)
int lcm(int a, int b)
{
return a * b / __gcd(a, b);
}
#define MAXN 10000001
int spf[MAXN];
void sieve()
{
spf[1] = 1;
for (int i = 2; i < MAXN; i++)
spf[i] = i;
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++)
{
if (spf[i] == i)
{
for (int j = i * i; j < MAXN; j += i)
if (spf[j] == j)
spf[j] = i;
}
}
}
vector<int> getFactorization(int x)
{
vector<int> ret;
while (x != 1)
{
ret.push_back(spf[x]);
x = x / spf[x];
}
return ret;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
sieve();
w(t)
{
int k, x;
cin >> k >> x;
vector<int> factors = getFactorization(x);
vector<int> vec;
int pro = 1;
int curr = factors[0];
sort(ALL(factors));
for (int i : factors)
{
if (curr == i)
{
pro *= i;
}
else
{
vec.push_back(pro);
curr = i;
pro = i;
}
}
vec.push_back(pro);
sort(ALL(vec));
if (vec.size() <= k)
{
int sm = 0;
for (int i : vec)
sm += i;
sm += (k - vec.size());
cout << sm << endl;
}
else
{
priority_queue<minheap> pq;
for (int i : vec)
{
pq.push(i);
}
FOR(i, 1, vec.size() - k)
{
int fir = pq.top();
pq.pop();
int sec = pq.top();
pq.pop();
pq.push(fir * sec);
}
int anss = 0;
while (!pq.empty())
{
anss += pq.top();
pq.pop();
}
cout << anss << endl;
}
}
return 0;
}
please tell me for what test case i am getting wrong answer.