Finding inverse

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <climits>
#include <cmath>
#include <functional>
#include <type_traits>
#include <fstream>
#include <bitset>
#include <complex>
#include <iomanip>
 
#define int long long
using namespace std;
 
#define cross(x, y) (((x)*conj(y)).imag())
#define sign(v) ((0 < (v)) - ((v) < 0))
 
int p(int a, int b, int m)
{
    if (b == 0) return 1;
    else if (b % 2 == 0) { int r = p(a, b/2, m); return (r*r) % m; }
    else return (p(a, b-1, m)*a) % m; 
}
int gdc(int a, int b)
{
    if (b == 0) return a;
    return gdc(b, a%b);
}
 
void solve()
{
    int a, m;
    cin >> a >> m;
 
    if (gdc(a, m) != 1)
    {
        cout << -1;
        return;
    }
 
    unordered_map<int, int> factors;
    int num = m;
    int top = sqrt(num);
    for (int i = 2; i <= top && i < num; i++)
    {
        while (num % i == 0)
        {
            factors[i]++;
            num /= i;
        }
    }
    if (num > 1)
        factors[num]++;
 
    // Calc phi
    int phi = 1;
    for (auto kv : factors)
        phi *= p(kv.first, kv.second-1, m) * (kv.first - 1);
 
    cout << p(a, phi-1, m) << '\n';
}
 
 
signed main()
{
    ios::sync_with_stdio(0);
    cout.precision(25);
    //setprecision(10);
    //cin.tie(0);
 
    int t = 1;
 
    cin >> t;
    //ifstream f("testcase.txt");
    //cin.rdbuf(f.rdbuf());
 
    for (int i = 0; i < t; i++)
    {
        solve();
        cout.flush();
    }
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: ACCEPTED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: TIME LIMIT EXCEEDED