We define a primitive root of prime number to be some integer satisfying the property that all values of where are different.
For example: if , we want to look at all values of in the inclusive range from to . For , the powers of (where is in the inclusive range from to ) are as follows:
Note that each of these evaluates to one of the six distinct integers in the range .
Given prime , find and print the following values as two space-separated integers on a new line:
- The smallest primitive root of prime .
- The total number of primitive roots of prime .
Need Help? Check out a breakdown of this process at Math Stack Exchange.
A single prime integer denoting .
Print two space-separated integers on a new line, where the first value is the smallest primitive root of and the second value is the total number of primitive roots of .
Sample Input 0
Sample Output 0
The primitive roots of are and , and no other numbers in satisfy our definition of a primitive root. We then print the smallest primitive root () followed by the total number of primitive roots ().