1.  Порядок

 Максимальна оцінка: 20 балів

Обмеження на час: 5 сек.

Обмеження на пам'ять: 32 MБ

Вхідний файл: order.dat

Вихідний файл: order.sol

Програма: order.*

 Нехай n - довільне натуральне число, а послідовність i₁, i₂, ... , i_n містить усі натуральні числа від 1 до n включно. Порушенням порядку у такій послідовності називають систему таких двох нерівностей, що справджуються: j < k та i_j > i_k. Якщо послідовність зростає, то кількість порушень порядку дорівнює 0. Якщо послідовність спадає, то така кількість дорівнює n(n - 1)/2. В усіх інших випадках ця кількість розташована між вказаними величинами.

         Завдання

Встановіть парність кількості порушень порядку послідовності.

Вхідні дані

У першому рядку вхідного файлу вказано кількість послідовностей m. Кожний з наступних m рядків містить натуральне число n і послідовність різних натуральних чисел від 1 до n включно: i₁, i₂, ... , i_n при 2 ≤ т ≤ 100, 2 ≤ n ≤ 1 048 576. У 50 % тестів n ≤ 4096.

Вихідні дані

Єдиний рядок вихідного файлу має містити число в шістнадцятковій системі числення, яке відповідає двійковому числу яке утворене з m символів - нулів або одиниць - без пропусків: k-й символ рядка - це залишок від ділення на 2 кількості порушень порядку k-ї послідовності, заданої (k + 1)-м рядком вхідного файлу.

Приклад

Пояснення (00110 )₂=(6)₁₆

2. Код Грея

Максимальна оцінка: 100 балів

Обмеження на час: 1 сек.

Обмеження на пам'ять: 32 MБ

Вхідний файл: grey.dat

Вихідний файл: grey.sol

Програма: grey.*

Кодом Грея називають непозиційну систему запису цілих натуральних чисел за допомогою двох символів 0 та 1 таким чином. Нуль кодують послідов­ністю нулів. При зростанні цілого числа:

• наймолодший 1-й розряд у послідовності символів змінюють у такій послі­дов­ності: 0, 1, після чого у наступний 2-й розряд записують 1, а наймолодший розряд змінюють уже у протилежному порядку;
• два наймолодші розряди змінюють у такому порядку: 00, 01, 11, 10, після чого у 3-й розряд записують 1, а два наймолодші розряди змінюють уже у протилежному порядку: 10, 11, 01, 00 ... ;
• k наймолодших розрядів змінюють у порядку, визначеному попередніми кро­ка­ми, після чого у наступний (k + 1)-й розряд записують 1, а молодші розряди змінюють уже у протилежному порядку.

Коди Грея довжини 4 чисел від 0 до 15 включно такі (записано у порядку зростання числа): 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.

Коди Грея двох послідовних натуральних чисел відрізняються лише в одно­му розряді. Це використовують для збільшення надійності роботи системи оптич­них фотодіодів при встановленні кута повороту дисків - носіїв інформації.

Завдання

Визначте код Грея натурального числа.

Вхідні дані

Вхідний файл містить лише десятковий запис натурального числа n при n < 10¹⁸.

Вихідні дані

Вихідний файл має містити код Грея числа n мінімальної довжини. Інакше кажучи, цей код має починатися з одиниці й містити j символів,

де 2^{j - 1} ≤ n < 2^j.

Приклади