Скоро на самой известной платформе по программированию (Topforces) будет проходить очень важное соревнование!
У авторов есть набор из \(n\) задач и они должны выбрать не более трех из них в контест. Красота \(i\)-й задачи равна \(a_i\). Авторы хотят составить самый красивый контест (другими словами, суммарная красота выбранных задач должна быть максимально возможной).
Но в подготовке контеста есть одна очень важная особенность: из-за некоторых предрассудков авторов красоты задач не могут делить друг друга. Иными словами, если красоты выбранных задач равны \(x, y, z\), тогда \(x\) не должен делиться ни на \(y\), ни на \(z\), \(y\) не должен делиться ни на \(x\), ни на \(z\) и \(z\) не должен делиться ни на \(x\), ни на \(y\). Если красоты выбранных задач равны \(x\) и \(y\), то \(x\) должен не делиться на \(y\) и \(y\) должен не делиться на \(x\). Любой контест, составленный из одной задачи, является хорошим.
Ваша задача — найти максимально возможную суммарную красоту контеста, составленного из не более трех задач из заданного набора.
Вам необходимо ответить на \(q\) независимых запросов.
Если Вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете отправлять свой код.