@RomanZemin

Олени не
Если бы вы, наши замечательные юные программисты, учились бы в школе 30 лет назад, то свои программы вы бы писали в тетрадях, а сочинение могло бы быть на такую странную тему как "Олени не". Очень тяжело понять, что же надо писать в таком сочинении, поэтому, мы дадим формальное определение.

Словом будем называть непустую последовательность заглавных или строчных букв алфавита. В этой задаче в качестве алфавита мы возьмем латиницу. Предложением будем называть последовательность слов, разделенных одним или несколькими пробелами. Будем говорить, что предложение соответствует теме "Олени не", если найдется последовательность, состоящая из одного или нескольких подряд идущих слов такая, что из нее можно получить фразу "Oleni ne" путем удаления или вставки пробелов, а также заменой строчных букв на заглавные и наоборот.

Задан набор предложений. Напишите программу для определения, какие из них соответствуют теме "Олени не".

Input format
В первой строке записано одно натуральное число n — количество предложений, n ≤ 100. Далее в n строках записаны предложения — по одному в каждой строке. Суммарная длина всех предложений не превосходит 3 мегабайт.

Output format
Для каждого из предложений выведите в одной строке число 0 или 1. Число 1 означает, что предложение соответствует теме.

Examples
Input Output
7
Oleni NE letaut
OLE OLE OLE OLE Nine salut
Dumayu o govyadine i olenine
O leni ne skazu
Ne oleni
Kole Nine salut
Oline ne
1
1
1
1
0
0
0
Notes
Пятое предложение не подходит, так как слова нельзя переставлять. Шестое предложение не подходит, так как фраза должна начинаться и заканчиваться строго на границе слова.

Методика проверки
Задача проверяется на 10 тестах. Прохождение каждого теста оценивается в 10 баллов. При этом в первых пяти тестах суммарная длина предложений не превосходит 10000. Кроме того, еще в трех тестах суммарная длина предложений не превосходит 1 мегабайта.

Submit a solution

0