Коди Грея отрималу свою назву за іменем Франка Грея (Frank Gray), фізіка з Bell Telephone Laboratories, який у 1930-х роках винайшов метод, у даний час використовуваний для передачі кольорового телевізійного сигналу, разом з існуючими методами передачі та отримання чорно-білого сигналу; тобто при отриманні кольорового сигналу чорно-білим приймачем зображення виводиться відтінками сірого кольору.

Хоча існує багато різних варіантів кодів Грея, розглянемо лише один: "двійковий відбитий (рефлексний) код Грея". Саме цей код як правило маєтьсяна увазі, коли говорять про неконкретний "код Грея".

Відбитий двійковий код Грея будується наступним чином. Починаємо з рядків 0 та 1, які подають відповідно цілі числа 0 та 1.

Візьмемо відбиття цих рядків відносно горизонтальної осі після наведеного списку і помістимо 1 ліворуч від нових записів списку, а ліворуч від вже наявних розмістимо 0.

Таким чином отримано відбитий код Грея для n = 2. Щоб отримати код для n = 3, повторимо описану процедуру і отримаємо:

При такому способі побудови легко побачити за індукцією по n, що, по-перше, кожна з 2n комбінацій бітів з'являється у списку, причому лише один раз; по-друге, при переході від одного елементу списку до того, який стоїть поряд, змінюється лише один біт; по-третє, лише один біт змінюється при переході від останнього елементу списку до першого. Коди Грея, які мають останню властивість, називаються циклічними, і відбитий код Грея обов'язково є таким.

Для кожного заданого числа k вивести десяткове значення k-го кода Грея.

Вхідні дані

У вхідному файлі міститься деякий набір тестових даних, кожне число k (0 ≤ k ≤ 1018) у наборі задано у окремому рядку. Кілбкість наборів даних у одному тесті не перевищує 105.

Вихідні дані

Для кожного заданого числа k вивести у окремому рядку десяткове значення k-го кода Грея.