纯情活泼的拆分

题号：NC222904
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

更好的阅读体验：

链接：https://pan.baidu.com/s/1o4smgWB19XF7_N_0SJ1R9Q ，提取码：dkq4 。

琪露诺学会了 $\mathtt{A+B\ problem}$ 和 $\mathtt{A^B\ problem}$ 。所以琪露诺打算将一个数进行拆分，来练习她学会的内容。以下会把这种拆分方式称作「纯情活泼的拆分」。

具体来说，她会把一个正整数 $\delta$ ，拆分成若干个互不相同的大于等于2的自然数的幂次和，即：

$\delta=p_1^{c_1}+p_2^{c_2}+\cdots =\sum p_i^{c_i}$

很显然地，对于一个 $\delta$ 可能存在若干种不同的拆分方式。为此，琪露诺定义了一个「纯情」值 $\varphi_\delta(p_1:c_1,p_2:c_2,\cdots)$ ，用于衡量一种拆分的价值。有：

$\varphi_\delta(p_1:c_1,p_2:c_2,\cdots)=c_1+c_2+\cdots =\sum c_i$

显然，对于每个 $\delta$ ，存在一种拆分方式使得它的「纯情」值最大，我们将这个最大值记为 $\delta$ 的「活泼」值，用 $\Phi(\delta)$ 表示。特别地，如果不存在任何一种合法的拆分方式，则 $\Phi(\delta)=9$ 。琪露诺为了验证她的拆分，找到了 $\mathit n$ 个数 $w_1,w_2,\cdots w_n$ 。你要做的就是分别求出 $\Phi(w_1),\Phi(w_2),\cdots \Phi(w_n)$ 。

输入描述:

第一行一个正整数  ，表示琪露诺找来的数的个数。
接下来一行， 个正整数  ，含义如题所示。

输出描述:

共  行。其中，第  行输出  。

示例1

输入

复制

4
5 7 19 23

输出

复制

说明

对于样例  的  ，存在以下一组可能的解：

 。
 。
 。
 。

可以证明，不存在比它们更优的拆分方案。

备注:


对于所有数据，有  。