{"problem":{"name":"A. 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":"CF871A"},"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]-th 个查询。\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]-th 个查询。\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"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ q \\in \\mathbb{Z} $ be the number of queries.  \nLet $ N = (n_1, n_2, \\dots, n_q) $ be the sequence of positive integers, where $ n_i \\in \\mathbb{Z}^+ $.  \nLet $ C \\subset \\mathbb{Z}^+ $ be the set of composite numbers: $ C = \\{ k \\in \\mathbb{Z}^+ \\mid k > 1 \\text{ and } k \\text{ is not prime} \\} $.  \n\n**Constraints**  \n1. $ 1 \\le q \\le 10^5 $  \n2. For each $ i \\in \\{1, \\dots, q\\} $: $ 1 \\le n_i \\le 10^9 $  \n\n**Objective**  \nFor each $ n_i $, find the maximum integer $ k \\ge 1 $ such that there exist $ c_1, c_2, \\dots, c_k \\in C $ satisfying:  \n$$\nn_i = \\sum_{j=1}^k c_j\n$$  \nIf no such representation exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF871A","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"}}