#include <vector>
#include <list>
#include <string>
#include <unordered_map>

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

using namespace std;

int nlz(unsigned x)
{
    int n;
    if (x == 0) return 32;
    n = 1;
    if ((x >> 16) == 0) { n = n + 16; x = x << 16; }
    if ((x >> 24) == 0) { n = n + 8; x = x << 8; }
    if ((x >> 28) == 0) { n = n + 4; x = x << 4; }
    if ((x >> 30) == 0) { n = n + 2; x = x << 2; }
    n = n - (x >> 31);
    return n;
}

int bitsize (int x)
{
    unsigned y = (unsigned)x;
    return 32 - nlz(x);
}

int main()
{
    int n = 999999;
    vector < bool > A(n, true);
    typedef unordered_map < string, vector < int > > res_t;
    res_t res;

    for (int i = 2; i < sqrt(n); ++i) {
        if (A[i]) {
            int k = 2, j = k * i;
            for (; j < n; ++k, j = k * i) {
                A[j] = false;
            }
        }
    }
    for (int i = 2; i < n; ++i) {
        if (A[i]) {
            char buf[1024];
            sprintf(buf, "%d", i);
            int digits = strlen(buf);
            int mask = 1;
            while (bitsize(mask) <= digits) {
                char smask[1024];
                char prev = 0;
                bool ok = true;
                strcpy(smask, buf);

                for (int k = 0; k < digits; ++k) {
                    if (mask & (1 << k)) {
                        if (!prev) {
                            prev = smask[k];
                        } else if (prev != smask[k]) {
                            ok = false;
                            break;
                        }
                        smask[k] = '*';
                    }
                }
                if (ok&&prev) {
                    res[smask].push_back(i);
                }
                mask ++;
            }
        }
    }

    res_t::iterator max_it = res.begin();
    for (res_t::iterator it = res.begin(); it != res.end(); ++it) {
        if (max_it->second.size() < it->second.size()) {
            max_it = it;
        }
    }
    printf("%s: %d:\n", max_it->first.c_str(), max_it->second.size());
    if (!max_it->second.empty()) printf(" ");
    for (int i = 0; i < (int)max_it->second.size(); ++i) {
        printf("%d ", max_it->second[i]);
    }
    if (!max_it->second.empty()) printf("\n");
}