284A.md (1384B)
1 Source: https://codeforces.com/problemset/problem/284/A 2 3 A. Cows and Primitive Roots 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 The cows have just learned what a primitive root is! Given a prime *p*, a primitive root  is an integer *x* (1 ≤ *x* < *p*) such that none of integers *x* - 1, *x*2 - 1, ..., *x**p* - 2 - 1 are divisible by *p*, but *x**p* - 1 - 1 is. 22 23 Unfortunately, computing primitive roots can be time consuming, so the cows need your help. Given a prime *p*, help the cows find the number of primitive roots . 24 25 Input 26 27 The input contains a single line containing an integer *p* (2 ≤ *p* < 2000). It is guaranteed that *p* is a prime. 28 29 Output 30 31 Output on a single line the number of primitive roots . 32 33 Examples 34 35 Input 36 37 ``` 38 3 39 ``` 40 41 Output 42 43 ``` 44 1 45 ``` 46 47 Input 48 49 ``` 50 5 51 ``` 52 53 Output 54 55 ``` 56 2 57 ``` 58 59 Note 60 61 The only primitive root  is 2. 62 63 The primitive roots  are 2 and 3.