Связь между математикой и биологией является достаточно сложной. Она не является достаточно очевидной, как может показаться на первый взгляд, но носит абстрактный характер, который не всегда легко установить.
Озеро Восток размером около 14000 квадратных километров, глубиной до 650 метров, и покрытое 3743 метрами льда недавно было открыто в Антарктиде. Озеро находилось под действием сильного давления, до него не доходил свет несколько миллионов лет. Считается, что обычная жизнь в нем эволюционировала к более эффективной форме при помощи генетического кода, состоящего из трех оснований (на данный момент имеются четыре основания - аденин, цитозин, гуанин и тимин). Пока не будут предложены разумные названия новых оснований, мы будем использовать для них сокращения N, O и P.
Геном имеет вид одной цепи и является направленным, то есть рассматривается как последовательность символов над алфавитом {N, O, P}. Во избежание нестабильности, геном должен удовлетворять свойству последовательности Туэ, согласно норвежскому математику A. Туэ (1863-1922). Подпоследовательностью заданной последовательности будем называть подряд идущую последовательность ее элементов. Две подпоследовательности будем называть соседними, если вторая следует сразу за первой. Последовательность называется последовательностью Туэ, если в ней никакие две соседние подпоследовательности не являются одинаковыми. Например, NOPNO таковой будет, а NOPNPNO не является последовательностью Туэ. Поэтому первая последовательность может быть геномом, а вторая нет.
Вы допущены к экспериментам по созданию геномов. Вам необходимо сгенерировать геномы заданной длины.
Входные данные состоят из нескольких тестов. Каждый тест состоит из единственного целого числа n (1 ≤ n ≤ 5000). За последним тестом следует ноль.
Для каждого входного значения n вывести в отдельной строке геном длины n. Если генома длины n не существует, то вывести пустую строку.