import java.io.*;
import java.util.*;

public class Tests {
    private static final int MAX_N = 1000;
    private static final int L = 9;
    private static final String SYMBOLS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890";
    private static final String MASK_SYMBOLS = SYMBOLS + "*";

    int testNo = 0;
    PrintWriter out;
    static PrintWriter descriptions;
    Random random = new Random(3583289570238423582L);

    void beginTest(String description, Object... args) {
        ++testNo;
        descriptions.format("%02d: %s\n", testNo, String.format(description, args));
        descriptions.flush();
        System.out.format("%02d: %s\n", testNo, String.format(description, args));
        try {
            out = new PrintWriter(String.format("tests/%02d", testNo));
        } catch (FileNotFoundException e) {
            throw new AssertionError(e);
        }
    }

    private void run() {
        test("Sample", "A**1MP19*", Arrays.asList("A001MP199", "E885EE098", "A111MP199", "KT7351TTB"));
        String mask1 = randomMask(3);
        test("Single matched", mask1, Arrays.asList(randomCode(mask1)));
        test("Single not matched", randomMask(4), Arrays.asList(randomCode()));
        test("Exact mask", "A57KJFHSJ", Arrays.asList("A57KJFHSJ", "A57KJ9HSJ", "A57KFJHSJ"));
        test("Wildcard mask", "*********", Arrays.asList("A57KJFHSJ", "A57KJ9HSJ", "A57KFJHSJ"));
        test("Shifted mask", "***ABC***", Arrays.asList("BCABCABCA", "ABCABCABC", "CABCABCAB"));

        randomTest(MAX_N, 0, 1);
        randomTest(MAX_N, L, MAX_N);
        randomTest(MAX_N, 7, 0);
        randomTest(MAX_N, 2, MAX_N / 2);
    }

    private void randomTest(int n, int stars, int matched) {
        beginTest("%d stars, %d codes, %d matched", stars, n, matched);
        String mask = randomMask(stars);
        List<String> codes = new ArrayList<>();
        for (int i = 0; i < matched; i++) {
            String code;
            do {
                code = randomCode(mask);
            } while (codes.contains(code));
            codes.add(code);
        }
        for (int i = matched; i < n; i++) {
            String code;
            do {
                code = randomCode();
            } while (codes.contains(code));
            codes.add(code);
        }
        Collections.shuffle(codes, random);
        endTest(mask, codes);
    }

    String randomMask(int stars) {
        String mask = randomCode();
        int[] permutation = permutation(L);
        for (int i = 0; i < stars; i++) {
            mask = replace(mask, permutation[i], '*');
        }
        return mask;
    }

    private String replace(String string, int index, char ch) {
        return string.substring(0, index) + ch + string.substring(index + 1);
    }

    int[] permutation(int n) {
        int[] permutation = new int[n];
        for (int i = 0; i < n; i++) {
            int j = random.nextInt(i + 1);
            permutation[i] = permutation[j];
            permutation[j] = i;
        }
        return permutation;
    }

    String randomCode(String mask) {
        String code = randomCode();
        for (int i = 0; i < L; i++) {
            char ch = mask.charAt(i);
            if (ch != '*') {
                code = replace(code, i, ch);
            }
        }
        return code;
    }

    private String randomCode() {
        String result = "";
        for (int i = 0; i < L; i++) {
            result += SYMBOLS.charAt(random.nextInt(SYMBOLS.length()));
        }
        return result;
    }

    private void test(String description, String mask, List<String> code) {
        beginTest(description);
        endTest(mask, code);
    }

    private void endTest(String mask, List<String> codes) {
        verifyString(mask, MASK_SYMBOLS);

        assert 1 <= codes.size() && codes.size() <= MAX_N;
        for (String code : codes) {
            verifyString(code, SYMBOLS);
        }

        assert new HashSet<>(codes).size() == codes.size() : "Duplicate codes";

        out.println(mask);
        out.println(codes.size());
        for (String code : codes) {
            out.println(code);
        }
        out.close();
    }

    private void verifyString(String string, String symbols) {
        assert string.length() == L;
        for (char ch : string.toCharArray()) {
            assert symbols.indexOf(ch) != -1;
        }
    }


    public static void main(String[] args) throws IOException {
        descriptions = new PrintWriter("tests/tests.lst");
        new Tests().run();
        descriptions.close();
    }
}
