Alkuluvut

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) 0xffff
#endif

#define SMALL_P 90808080

int nums[11];
char numsc[11];
vector<ll> smallPrimes;
bool issp[SMALL_P];

bool isPrime(ll x) {
  if (x < 2) return false;
  if (x % 2 == 0) return x == 2;
  if (x % 3 == 0) return false;
  if (x % 5 == 0) return false;
  if (x > 10000000000000000LL) return false;
  for (ll pr : smallPrimes) {
    ll bp = pr * pr;
    if (x < bp) return true;
    if (x % pr == 0) return false;
  }
  return true;
}

bool permuteDrop(const string& s) {
  if (s[0] == '0') return true;

  if (s.back() == '0' || s.back() == '2' || s.back() == '4' || s.back() == '5' ||
      s.back() == '6' || s.back() == '8') return true;

  return false;
}

ll to_ll(const string& s) {
  ll val = 0;
  for (char c : s) val = (val * 10LL) + ll(c - '0');
  return val;
}

void solve() {
  int n;
  cin>>n;

  bool hasOkDigit = false;
  string S;

  for (int i = 0; i < n; i++) {
    cin>>nums[i];
    numsc[i] = (char)(nums[i]+48);
    S += to_string(nums[i]);

    // cout << S << "\n";
    // cout << numsc[i]<<" CHAR\n";
    hasOkDigit |= nums[i] == 1 || nums[i] == 3 || nums[i] == 7 || nums[i] == 9;
  }

  sort(S.begin(), S.end());

  if (!hasOkDigit) return void(cout << "NO\n");

  string ans;

  function<void(string&, int)> populateString = [&](string& s, int dep) {
    if (dep == 0) return;
    
    if (s.size() == 16) return;

    if (ans.empty() && s[0] != '0' && isPrime(to_ll(s))) {
      ans = s;
      return;
    }

    int digit = numsc[rand() % n];
    int pos = rand() % S.size();
    // cout << "adding digit "<<digit<<" to pos "<<pos<<" resulting in: ";
    s.insert(s.begin() + pos, digit);
    // cout << s << "\n";
    populateString(s, dep - 1);
    s.erase(s.begin() + pos);
  };

  // take digits, permute and add from set while keeping valid?
  do {
    if (permuteDrop(S)) continue;
    
    for (int tries = 0; tries <= 10101; tries++) {
      // pick a random index (not last) and random digit from selection
      string s = S;
      populateString(s, 17 - S.size() + 1);
      if (!ans.empty()) return void(cout << "YES\n" << ans << "\n");
    }
  } while (next_permutation(S.begin(), S.end()));

  cout << "NO\n";
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  srand(time(0));

  // guess: no prime is suuper big?
  fill(issp, issp+SMALL_P, true);

  issp[0] = false;
  issp[1] = false;
  for (ll j = 2; j * j < SMALL_P; j++) {
    if (issp[j]) {
      for (ll x = j * j; x < SMALL_P; x += j) issp[(int)x] = false;
    }
  }

  for (int x = 2; x < SMALL_P; x++) {
    if (issp[x]) smallPrimes.push_back(x);
  }

  int t; cin>>t;
  while (t--) {
    solve();
  }
}

Test 1

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED