{"raw_statement":[{"iden":"statement","content":"Birute loves modular arithmetics, but hates long problem statements.\n\n\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"},{"iden":"input","content":"The 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). "},{"iden":"output","content":"For 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)_."},{"iden":"examples","content":"Input212OutputCase #1: 1Case #2: 0"},{"iden":"note","content":"_Fun fact: 1 is neither prime nor composite number._"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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 $.","simple_statement":"Given a set of the first N positive integers, find the largest subset where every pair of numbers is coprime (GCD = 1). Print the size of this subset for each test case.","has_page_source":false}