I could solve it using trivial bruteforce. But I get TL, using more clever and probably expected solution. I used this:

https://e-maxx.ru/algo/discrete_root (Read only first section, we don't need anything else). The slowest part here is Discrete Logarithm, which I calculate in \sqrt{n} * log_from_map.