{"raw_statement":[{"iden":"statement","content":"Numbers\n\nYou're working with large numbers, and you want to calculate the totient function of a certain one. The totient function of a number $n$ is defined as the number of positive integers less than or equal $n$ that are relatively prime with $n$, i.e. the number of integers $k$ such that $k$ <= $n$ and $g c d (k, n) = 1$.\n\nFor example, the totient of $15$ is $8$, because 1, 2, 4, 7, 8, 11, 13, and 14 are relatively prime with $15$, while 3, 5, 6, 9, 10, 12, and 15 are not. 4 is relatively prime with 15, because there aren't any common factors of 4 and 15. 4 has factors {2}, and 15 has factors {3, 5}. On the other hand, 10 is not relatively prime with 15, because 10 and 15 both have a common factor of 5.\n\nGiven an integer $n$, figure out the value of $φ (n)$, where $φ$ represents the totient function as described above.\n\nThe only line of input contains a single positive integer $n$ less than 1000.\n\nOutput a single positive integer $p$: the value of $φ (n)$ as described above.\n\n"},{"iden":"input","content":"The only line of input contains a single positive integer $n$ less than 1000."},{"iden":"output","content":"Output a single positive integer $p$: the value of $φ (n)$ as described above."},{"iden":"examples","content":"Input15\nOutput8\nInput60\nOutput16\nInput7\nOutput6\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ n < 1000 $.  \nLet $ \\varphi(n) $ denote Euler’s totient function: the count of integers $ k \\in \\{1, 2, \\dots, n\\} $ such that $ \\gcd(k, n) = 1 $.\n\n**Constraints**  \n$ 1 \\leq n < 1000 $\n\n**Objective**  \nCompute:  \n$$\n\\varphi(n) = \\left| \\left\\{ k \\in \\mathbb{Z} \\mid 1 \\leq k \\leq n \\text{ and } \\gcd(k, n) = 1 \\right\\} \\right|\n$$","simple_statement":"Given a positive integer n less than 1000, count how many positive integers from 1 to n are relatively prime to n (i.e., their GCD with n is 1). Print that count.","has_page_source":false}