#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
int n;
int dp[N][N];
vector<int> prime;

void primes() {
    // 用欧拉筛模板，线性时间复杂度生成n以内素数表，相当于完全背包问题的物品表，区别是01背包物品只能拿一次，完全背包无限次
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    prime.push_back(-1); // 占位符，使素数从 prime[1] 开始
    for (int i=2; i<=n; ++i) {
        if (is_prime[i]) {
            prime.push_back(i); // 素数从 prime[1] 开始存储
        }
        // 从第2个元素（prime[1]）开始遍历，跳过占位符
        for (int j=1; j<prime.size() && i*prime[j]<=n; ++j) {
            is_prime[i * prime[j]] = false;
            if (i % prime[j] == 0) break;
        }
    }
}
int dfs(int u,int num)...