{"problem":{"name":"C. Maximum splitting","description":{"content":"You are given several queries. In the _i_\\-th query you are given a single positive integer _n__i_. You are to represent _n__i_ as a sum of maximum possible number of composite summands and print this","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF872C"},"statements":[{"statement_type":"Markdown","content":"You are given several queries. In the _i_\\-th query you are given a single positive integer _n__i_. You are to represent _n__i_ as a sum of maximum possible number of composite summands and print this maximum number, or print _\\-1_, if there are no such splittings.\n\nAn integer greater than 1 is composite, if it is not prime, i.e. if it has positive divisors not equal to 1 and the integer itself.\n\n## Input\n\nThe first line contains single integer _q_ (1 ≤ _q_ ≤ 105) — the number of queries.\n\n_q_ lines follow. The (_i_ + 1)-th line contains single integer _n__i_ (1 ≤ _n__i_ ≤ 109) — the _i_\\-th query.\n\n## Output\n\nFor each query print the maximum possible number of summands in a valid splitting to composite summands, or _\\-1_, if there are no such splittings.\n\n[samples]\n\n## Note\n\n12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, but the first splitting has the maximum possible number of summands.\n\n8 = 4 + 4, 6 can't be split into several composite summands.\n\n1, 2, 3 are less than any composite number, so they do not have valid splittings.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你将得到若干查询。在第 #cf_span[i]-th 个查询中，给你一个正整数 #cf_span[ni]。你需要将 #cf_span[ni] 表示为尽可能多的合数加数之和，并输出这个最大数量；如果不存在这样的划分，则输出 _-1_。\n\n一个大于 #cf_span[1] 的整数是合数，当且仅当它不是素数，即它具有不等于 #cf_span[1] 和其自身的正因数。\n\n第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105]) —— 查询的数量。\n\n接下来 #cf_span[q] 行，第 (#cf_span[i + 1])-th 行包含一个整数 #cf_span[ni] (#cf_span[1 ≤ ni ≤ 109]) —— 第 #cf_span[i] 个查询。\n\n对于每个查询，输出在合法的合数加数划分中可能的最大加数个数，或 _-1_（如果不存在这样的划分）。\n\n#cf_span[12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12]，但第一个划分具有最多的加数个数。\n\n#cf_span[8 = 4 + 4]，#cf_span[6] 无法被划分为多个合数加数。\n\n#cf_span[1, 2, 3] 小于任何合数，因此它们没有合法的划分。\n\n## Input\n\n第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105]) —— 查询的数量。#cf_span[q] 行 follow。第 (#cf_span[i + 1])-th 行包含一个整数 #cf_span[ni] (#cf_span[1 ≤ ni ≤ 109]) —— 第 #cf_span[i] 个查询。\n\n## Output\n\n对于每个查询，输出在合法的合数加数划分中可能的最大加数个数，或 _-1_（如果不存在这样的划分）。\n\n[samples]\n\n## Note\n\n#cf_span[12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12]，但第一个划分具有最多的加数个数。#cf_span[8 = 4 + 4]，#cf_span[6] 无法被划分为多个合数加数。#cf_span[1, 2, 3] 小于任何合数，因此它们没有合法的划分。","is_translate":true,"language":"Chinese"}],"meta":{"iden":"CF872C","tags":["dp","greedy","math","number theory"],"sample_group":[["1\n12","3"],["2\n6\n8","1\n2"],["3\n1\n2\n3","\\-1\n-1\n-1"]],"created_at":"2026-03-03 11:00:39"}}