- Practice
- Mathematics
- Number Theory
- Primitive Problem

# 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:

- 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.

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