Submission

Score: 0

User: C12

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.027 second

Submitted On: 2026-01-21 09:12:56

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

#define f first
#define s second
#define pii pair<ll,ll>
#define puii pair<ull,ull>
#define piii pair<ll,pii>
#define tiiii tuple<ll,ll,ll,ll>
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define mt make_tuple
 
#define mpiiii(a,b,c) make_pair(a,make_pair(b,c));
// ll mod = 1000000007;
ll m;
string t,neww;
ll num;

const ll n = 10 * 1000 * 1000;

int8_t p[n] = {0};
ll cnt = 0;

int pos[6];
int checkpos[9];

set<ll>st;

map<string,ll>mapp;
ll power[6] = {1,10,100,1000,10000,10000};

int custom_stoi(string st)
{
    int digit = 1, sum = 0;
    for (int i = st.length() - 1; i >= 0; i--)
    {
        sum += digit * (st[i] - '0');
        digit *= 10;
    }
    return sum;
}

void recursive(int i){
    if(i == m){
        // ll power = 1;
        num = 0;
        // for(int j = 0;j < m;j++){
        //     num += (int(t[pos[j]]) - int('0')) * power[j];
        //     // power *= 10;
        // }

        num = custom_stoi(t);
        
        // cout << num << '\n';
        if(p[num] == 0 && st.find(num) == st.end()){
            cnt++;
            st.insert(num);
        }
    }
    for(int j = 0;j < m;j++){
        if(checkpos[j]) continue;
        checkpos[j] = 1;
        pos[i] = j;
        recursive(i+1);
        checkpos[j] = 0;
    }
}

void solve(){
    cin >> t;
    
    sort(t.begin(),t.end());
    
    int i,j;
    for(i = 0;i < t.length();i++){
        if(!(t[i] < '0' || t[i] > '9')) break;
    }
    for(j = t.length()-1;j >= 0;j--){
        if(!(t[i] < '0' || t[i] > '9')) break;
    }
    t = t.substr(i,j-i+1);

    // if(t.length() != m) ll j = 1/0;
    
    // cout << i << ' ' << j << ' ' << t << '\n';
    if(mapp.find(t) != mapp.end()){
        cout << mapp[t] << '\n';
        // cout << "Y";
        return;
    }

    st.clear();

    cnt = 0;
    recursive(0);
    cout << cnt << '\n';

    mapp[t] = cnt;

    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << "start";

    for(ll i = 2;i*i < n;i++){
        if(p[i] == 1) continue;
        for(ll j = i;i*j < n;j++){
            // cout << (i*j) << '\n';
            p[i*j] = 1;
        }
    }

    // cout << "finish\n";

    ll q;
 
    cin >> q >> m;

    while(q--)
        solve(); 

    return 0;
}
/*
4 
2
13
97
12
91

10
3
013
113
302
312
313
013
113
302
312
313

*/