We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. Primitive Problem

Primitive Problem

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:

  1. The smallest primitive root of prime .
  2. The total number of primitive roots of prime .

Need Help? Check out a breakdown of this process at Math Stack Exchange.

Input Format

A single prime integer denoting .

Constraints

Output Format

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

7

Sample Output 0

3 2

Explanation 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 ().