{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"The 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."},{"iden":"output","content":"For each query print the maximum possible number of summands in a valid splitting to composite summands, or _\\-1_, if there are no such splittings."},{"iden":"examples","content":"Input\n\n1\n12\n\nOutput\n\n3\n\nInput\n\n2\n6\n8\n\nOutput\n\n1\n2\n\nInput\n\n3\n1\n2\n3\n\nOutput\n\n\\-1\n-1\n-1"},{"iden":"note","content":"12 = 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."}],"translated_statement":[{"iden":"statement","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] 小于任何合数，因此它们没有合法的划分。"},{"iden":"input","content":"第一行包含一个整数 #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] 个查询。"},{"iden":"output","content":"对于每个查询，输出在合法的合数加数划分中可能的最大加数个数，或 _-1_（如果不存在这样的划分）。"},{"iden":"examples","content":"输入112输出3输入268输出12输入3123输出-1-1-1"},{"iden":"note","content":"#cf_span[12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12]，但第一个划分具有最多的加数。#cf_span[8 = 4 + 4]，#cf_span[6] 无法被划分为多个合数加数。#cf_span[1, 2, 3] 小于任何合数，因此它们没有合法的划分。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \nFor each query $ i \\in \\{1, \\dots, q\\} $, let $ n_i \\in \\mathbb{Z}^+ $ be the integer to be decomposed.  \nLet $ \\mathcal{C} = \\{ k \\in \\mathbb{Z} \\mid k > 1 \\text{ and } k \\text{ is composite} \\} $ be the set of composite numbers.\n\n**Constraints**  \n1. $ 1 \\le q \\le 10^5 $  \n2. For each $ i $, $ 1 \\le n_i \\le 10^9 $\n\n**Objective**  \nFor each $ n_i $, find the maximum integer $ m \\ge 1 $ such that there exist $ c_1, c_2, \\dots, c_m \\in \\mathcal{C} $ satisfying:  \n$$\n\\sum_{j=1}^m c_j = n_i\n$$  \nIf no such decomposition exists, output $ -1 $.","simple_statement":null,"has_page_source":false}