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)