Задание

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

— символ «?» означает ровно одну произвольную цифру (0, 1, 2, 3, 4, 5, 6, 7, 8, 9);

— символ «Ч» означает ровно одну произвольную чётную цифру (0, 2, 4, 6, 8);

— символ «Н» означает ровно одну произвольную нечётную цифру (1, 3, 5, 7, 9);

— символ «П» означает трёхзначное простое число (101, 103, 107, 109, ..., 997);

— символ «К» означает не превосходящее 9999 число, являющееся квадратом (1, 4, 9, 16, 25, ..., 9801);

— символ «*» означает любую последовательность цифр произвольной длины, в том числе «*» может задавать и пустую последовательность.

Например, маске П?К?ЧН* соответствуют числа:

10703602745 (107-0-36-0-2-7-45), 109049085745012345 (109-0-49-0-8-5-745012345) и другие.

Найдите все натуральные числа, не превосходящие 109, соответствующие маске ППKК,  имеющие нечётное число делителей  и кратные числу 13.

Пояснение.  Число p является делителем числа N, если число N кратно p.

Так, у числа 12 всего 6 делителей: 1, 2, 3, 4, 6, 12.