The problem asks you to find largest primitive root modulo prime.

The algorithm for finding smallest one can be found here
https://e-maxx-eng.appspot.com/algebra/primitive-root.html

An easy modification (flipping one of for-loops) yield an AC.