Математик Василий

Математик Василий

Имя входного файла: vasiliy.in

Имя выходного файла: vasiliy.out

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 МБ

Юный математик Василий решил найти все простые числа, не превосходящие 10100. Для этого он написал программу, которая с помощью суперкомпьютера способна определять простоту числа практически мгновенно – за О(1).

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

Исходные данные

В первой строке задается натуральное число N (1 ≤ N ≤ 104) – количество запросов. Следующие N строк содержат по одному запросу – целому неотрицательному xi (xi ≤ 106) – число, простоту которого необходимо определить.

Результат

Для каждого запроса в отдельной строке необходимо вывести «Prime» (без кавычек), если соответствующее число является простым, и «Not prime» в противном случае.

Пример

Input	Output
4 1 3 9 15	Not prime Prime Not prime Not prime

Критерии оценки

Решение, верно находящее ответ при N не превосходящем 100, оценивается в 40 баллов.

Задача B. Делители

Имя входного файла: divisors.in

Имя выходного файла: divisors.out

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 МБ

Маша, Таня, Ирина, Катя и Аня играют в игру «делители». Они вместе выбирают некоторое число N, после чего по очереди называют по одному делителю числа N!, причем первой делитель называет Маша, второй – Таня, затем Ирина, потом Катя и, наконец, Аня. Проигрывает та из девочек, которая не может назвать делитель (все делители уже были названы).

Девочкам очень нравится эта игра, однако они быстро поняли, что исход игры зависит только от выбранного числа N. Теперь им не хочется искать все делители, а хочется сразу определить, кто же проиграет. Помогите девочкам!

Напомним, что число N! называется «факториалом» числа N и определяется как произведение всех чисел от 1 до N. Например, 4! = 1 × 2 × 3 × 4 = 24.

Исходные данные

В единственной строке задается натуральное число N (1 ≤ N ≤ 200) – число, выбранное девочками.

Результат

Выведите «Masha», если при заданном N проиграет Маша, «Tania», если проиграет Таня, «Irina» – в случае проигрыша Ирины, «Katya» – если проиграет Катя, «Anya» – если проиграет Аня.

Пример

input	output
2	Irina
3	Anya

Критерии оценки

Решение, верно находящее ответ при N не превосходящем 10 будет оценено не менее чем в 30 баллов. Если ваше решение будет верно решать задачу при N не более 20, то оно будет оценено в 60 баллов.