У Поликарпа есть t сейфов. Паролем от каждого сейфа является квадратная матрица из десятичных цифр '0' ... '9' (размеры паролей сейфов могут различаться). Увы, Поликарп забыл все пароли, и теперь ему предстоит их восстановить.

Поликарп любит простые числа, поэтому, когда он выбирал матрицы-пароли, он в каждую строку каждой матрицы вписал по простому числу. К своему удивлению, он обнаружил, что все матрицы получились симметричными (то есть после транспонирования остаются неизменными). Сейчас, годы спустя, к своей досаде Поликарп осознал, что он помнит только простые числа p_i, записанные в первых строках матриц-паролей.

Для каждого сейфа найдите количество матриц, которые могут быть паролем к нему.

Количество цифр в p_i определяет количество строк и столбцов i-ой матрицы. Одно простое число может содержаться сразу в нескольких строках матрицы-пароля или в нескольких матрицах. Простые числа, записанные не в первой строке матрицы, могут иметь ведущие нули.