This solution with python , but has some test faild because of Time limit exceeded .

import math

import os

import random

import re

import sys

def power(x, y, p):

result = 1

x = x % p

while y > 0:

if y & 1:

result = (result * x) % p

y = y >> 1

x = (x * x) % p

return result

def is_primitive_root(g, p, factors):

for factor in factors:

if power(g, (p - 1) // factor, p) == 1:

return False

return True

def find_primitive_roots(p):

primitive_roots = []

factors = set()

# Find prime factors of p-1

for i in range(2, int(math.sqrt(p-1)) + 1):

if (p - 1) % i == 0:

factors.add(i)

factors.add((p - 1) // i)

for g in range(2, p):

if is_primitive_root(g, p, factors):

primitive_roots.append(g)

return primitive_roots

def smallest_primitive_root(p):

primitive_roots = find_primitive_roots(p)

return min(primitive_roots)

if name == 'main':

p = int(input().strip())

smallest_root = smallest_primitive_root(p)

total_roots = len(find_primitive_roots(p))

print(smallest_root, total_roots)