{"problem":{"name":"G. Pairs","description":{"content":"The pair in the land of 1000000007 is the pair of numbers _a_ and _b_ with the following relation: a × b = 1 (mod 1000000007). It is believed to be the sign of divine. Your task is to increase the num","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10048G"},"statements":[{"statement_type":"Markdown","content":"The pair in the land of 1000000007 is the pair of numbers _a_ and _b_ with the following relation: a × b = 1 (mod 1000000007). It is believed to be the sign of divine. Your task is to increase the number of happy marriages so you must find the maximum number of distinct pairs! Distinct pairs can not have the same number (with the same index). Pairs are different when the sets of their indices are different\n\nThe first line contains the number of test cases _T_ (T ≤ 5). The first line of each test case contains the size of population, _n_ (1 ≤ n ≤ 30000). The following n lines contain the numbers ai (1 ≤ ai < 1000000007).\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 maximum number of distinct pairs.\n\n## Input\n\nThe first line contains the number of test cases _T_ (T ≤ 5). The first line of each test case contains the size of population, _n_ (1 ≤ n ≤ 30000). The following n lines contain the numbers ai (1 ≤ ai < 1000000007).\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 maximum number of distinct pairs.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ p = 1000000007 $.  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the population size.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,n_k}) $ be a sequence of integers where $ 1 \\le a_{k,i} < p $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 5 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_k \\le 30000 $  \n   - $ 1 \\le a_{k,i} < p $ for all $ i \\in \\{1, \\dots, n_k\\} $  \n\n**Objective**  \nFind the maximum number of distinct unordered pairs $ \\{i, j\\} $ with $ i \\ne j $ such that:  \n$$\na_{k,i} \\cdot a_{k,j} \\equiv 1 \\pmod{p}\n$$  \nand no index appears in more than one pair.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10048G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}