{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"We say that integer x, 0 \u0026lt; x \u0026lt; p, is a primitive root modulo odd prime p if and only if the set { (x\u003csup\u003ei\u003c/sup\u003e mod p) | 1 \u0026lt;\u003d i \u0026lt;\u003d p-1 } is equal to { 1, ..., p-1 }. For example, the consecutive powers of 3 modulo 7 are 3, 2, 6, 4, 5, 1, and thus 3 is a primitive root modulo 7.\r\u003cbr\u003eWrite a program which given any odd prime 3 \u0026lt;\u003d p \u0026lt; 65536 outputs the number of primitive roots modulo p.\r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Each line of the input contains an odd prime numbers p. Input is terminated by the end-of-file seperator."}},{"title":"Output","value":{"format":"HTML","content":"For each p, print a single number that gives the number of primitive roots in a single line."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e23\r\n31\r\n79\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n8\r\n24\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}