{"problem":{"name":"D. Modulo maths","description":{"content":"Birute loves modular arithmetics, but hates long problem statements. Given _n_, find _f(n)_. The first line contains the number of test cases _T_ (T ≤ 50). In the following _T_ lines there are int","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10049D"},"statements":[{"statement_type":"Markdown","content":"Birute loves modular arithmetics, but hates long problem statements.\n\nGiven _n_, find _f(n)_.\n\nThe first line contains the number of test cases _T_ (T ≤ 50). In the following _T_ lines there are integer values of number _n_ (1 ≤ n ≤ 10007). \n\nFor each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the value of _f(n)_.\n\n_Fun fact: 1 is neither prime nor composite number._\n\n## Input\n\nThe first line contains the number of test cases _T_ (T ≤ 50). In the following _T_ lines there are integer values of number _n_ (1 ≤ n ≤ 10007). \n\n## Output\n\nFor each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the value of _f(n)_.\n\n[samples]\n\n## Note\n\n_Fun fact: 1 is neither prime nor composite number._","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ i \\in \\{1, \\dots, T\\} $, let $ N_i \\in \\mathbb{Z} $ denote the input integer, and define the set $ S_i = \\{1, 2, \\dots, N_i\\} $.\n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. For each $ i \\in \\{1, \\dots, T\\} $, $ 1 \\le N_i \\le 10^6 $\n\n**Objective**  \nFor each test case $ i $, find the maximum size $ p_i $ of a subset $ S_i' \\subseteq S_i $ such that for all distinct $ a, b \\in S_i' $, $ \\gcd(a, b) = 1 $.  \nOutput $ p_i $ for each $ i $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10049D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}