У Поликарпа есть t сейфов. Паролем от каждого сейфа является квадратная матрица из десятичных цифр '0' ... '9' (размеры паролей сейфов могут различаться). Увы, Поликарп забыл все пароли, и теперь ему предстоит их восстановить.
Поликарп любит простые числа, поэтому, когда он выбирал матрицы-пароли, он в каждую строку каждой матрицы вписал по простому числу. К своему удивлению, он обнаружил, что все матрицы получились симметричными (то есть после транспонирования остаются неизменными). Сейчас, годы спустя, к своей досаде Поликарп осознал, что он помнит только простые числа pi, записанные в первых строках матриц-паролей.
Для каждого сейфа найдите количество матриц, которые могут быть паролем к нему.
Количество цифр в pi определяет количество строк и столбцов i-ой матрицы. Одно простое число может содержаться сразу в нескольких строках матрицы-пароля или в нескольких матрицах. Простые числа, записанные не в первой строке матрицы, могут иметь ведущие нули.
Выходные данные
Выведите t чисел, i-ое из которых является количеством матриц, которые могут быть паролем к i-ому сейфу. Числа выводите на отдельных строках.
Примечание
Пример возможной матрицы-пароля для второго сейфа:
239
307
977
Пример возможной матрицы-пароля для четвертого сейфа:
9001
0002
0002
1223