E. Медвежатник Поликарп
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

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

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

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

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

Входные данные

В первой строке входных данных записано целое число t (1 ≤ t ≤ 30) — количество сейфов. Далее в t строках записаны целые числа pi (10 ≤ pi ≤ 99999), pi — простое число, записанное в первой строке матрицы-пароля для i-ого сейфа. Все pi не содержат ведущих нулей.

Выходные данные

Выведите t чисел, i-ое из которых является количеством матриц, которые могут быть паролем к i-ому сейфу. Числа выводите на отдельных строках.

Примеры
Входные данные
4
11
239
401
9001
Выходные данные
4
28
61
2834
Примечание

Пример возможной матрицы-пароля для второго сейфа:


239
307
977

Пример возможной матрицы-пароля для четвертого сейфа:


9001
0002
0002
1223