可以证明，有且仅有 $n=1,3$ 无解。显然因为有 $2$ 故偶数均有解。$\forall x\ge 5,x\in N$，其至少可以拆分为 $x=5+y$，其中 $y$ 是零或偶数。

直观上看，要使得解最优，一定会以 $7\to 5\to 2$ 的优先级取硬币。

通过打表，可以直观地发现，当 $n \ge 14$ 时，数字每七个一组呈现出规律性，对 $n=7k+0,7k+1,\cdots,7k+6$，答案为 $k,k+1,k+1,k+1,k+2,k+1,k+2$。根据该规律可以求解出答案($n < 14$ 特判)。复杂度 $O(1)$。

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld", &x)
typedef long long ll;
ll n, a[] = {-1, -1, 1, -1, 2, 1, 3, 1, 4, 2, 2, 3, 2, 4, 2}, t;
ll r[] = {0, 1, 1, 1, 2, 1, 2};
signed main()
{
    for (sc(t); t; t--)
    {
        sc(n);
        if (n < 14)
        {
            printf("%lld\n", a[n]);
            continue;
        }
        printf("%lld\n", n / 7 + r[n % 7]);
    }
    return 0;
}

严格证明：根据无限背包 DP 的表达式，可知： $dp_i=1+\min(dp_{i-2},dp_{i-5},dp_{i-7})$ 首先根据暴力计算，可知 $[0,14)$ 内 $dp_{7k+r}$ 答案如下表：

可以先根据前面无规律的结果暴力求解出第二列：

直观计算，对 $x=3$，分类讨论：

• $r=0,dp_{3\cdot7+0}=1+\min(dp_{2\cdot7+5},dp_{2\cdot7+2},dp_{2\cdot7+0})=1+\min(3,3,2)=3$
• $r=1,dp_{3\cdot7+1}=1+\min(dp_{2\cdot7+6},dp_{2\cdot7+3},dp_{2\cdot7+1})=1+\min(4,3,3)=4$
• $r=2,dp_{3\cdot7+2}=1+\min(dp_{3\cdot7+0},dp_{2\cdot7+4},dp_{2\cdot7+2})=1+\min(3,4,3)=4$
• $r=3,dp_{3\cdot7+3}=1+\min(dp_{3\cdot7+1},dp_{2\cdot7+5},dp_{2\cdot7+3})=1+\min(4,3,3)=4$
• $r=4,dp_{3\cdot7+4}=1+\min(dp_{3\cdot7+2},dp_{2\cdot7+6},dp_{2\cdot7+4})=1+\min(4,4,4)=5$
• $r=5,dp_{3\cdot7+5}=1+\min(dp_{3\cdot7+3},dp_{3\cdot7+0},dp_{2\cdot7+5})=1+\min(4,4,3)=4$
• $r=6,dp_{3\cdot7+5}=1+\min(dp_{3\cdot7+4},dp_{3\cdot7+1},dp_{2\cdot7+6})=1+\min(5,4,4)=5$

更一般地，假设我们已知 $dp$ 的前七项 $dp_{7(k-1)+r}$ 为 $k,k+1,k+1,k+1,k+2,k+1,k+2$

那么跟上面分类讨论同理的做法，可以求得下七项 $dp_{7k+r}$ 为

$k+1,k+2,k+2,k+2,k+3,k+2,k+3$

即： $\begin{cases} dp_{k\cdot7+0} &=1+\min(dp_{(k-1)\cdot7+5}+dp_{(k-1)\cdot7+2}+dp_{(k-1)\cdot7+0}) =1+\min(k+1k+1k)=k+1 \\ dp_{k\cdot7+1} &=1+\min(dp_{(k-1)\cdot7+6}+dp_{(k-1)\cdot7+3}+dp_{(k-1)\cdot7+1}) =1+\min(k+2k+1k+1)=k+2 \\ dp_{k\cdot7+2} &=1+\min(dp_{k\cdot7+0}+dp_{(k-1)\cdot7+4}+dp_{(k-1)\cdot7+2}) =1+\min(k+1k+2k+1)=k+2 \\ dp_{k\cdot7+3} &=1+\min(dp_{k\cdot7+1}+dp_{(k-1)\cdot7+5}+dp_{(k-1)\cdot7+3}) =1+\min(k+2k+1k+1)=k+2 \\ dp_{k\cdot7+4} &=1+\min(dp_{k\cdot7+2}+dp_{(k-1)\cdot7+6}+dp_{(k-1)\cdot7+4}) =1+\min(k+2k+2k+2)=k+3 \\ dp_{k\cdot7+5} &=1+\min(dp_{k\cdot7+3}+dp_{k\cdot7+0}+dp_{(k-1)\cdot7+5}) =1+\min(k+2k+2k+1)=k+2 \\ dp_{k\cdot7+6} &=1+\min(dp_{k\cdot7+4}+dp_{k\cdot7+1}+dp_{(k-1)\cdot7+6}) =1+\min(k+3k+2k+2)=k+3 \\ \end{cases}$ 那么根据数学归纳法，可以得出结论：$k\ge 2,r\in[0,6],k,r\in Z$ 时，有： $dp_{7k+r}={k,k+1,k+1,k+1,k+2,k+1,k+2}$

TODO: 能否将 $O(1)$ 推广到较为一般的情况，对小的 n 或互质的 a，总能找出一个通式，从而取代无限背包