Китайская игра «Цзяньшидзы»

В древнем Китае было придумано множество интересных игр. Все знают очень известную игру «Majong». В данной задаче мы рассмотрим другую интересную китайскую игру «Цзяньшидзы». Кратко сформулируем правила игры:

Из двух куч каменей, двое играющих поочередно могут брать:

1. Произвольное ненулевое число камней из одной кучи.
2. Одновременно по одинаковому произвольному ненулевому числу камней из обеих куч.

Выигрывает тот, кто возьмет своим ходом последний камень.

Не сложно определить в каких случаях выигрывает первый, а в каких случаях выигрывает второй игрок. Задача сводится к нахождению так называемых проигрышных пар (a_i, b_i), означающих, что при кучах камней содержащих a_i и b_i камней проигрывает тот, кто в данный момент совершает свой ход. Вам предстоит решить эту задачу, но немного в другом виде.

Обозначим проигрышную, для ходящего позицию, когда в кучках a и b камней (a, b). Так как порядок куч не играет роли, то всегда будем считать, что a ≤ b. Упорядочим все проигрышные позиции в лексикографическом порядке, иначе говоря:

(a₁, b₁) < (a₂, b₂), если (a₁< a₂) или ((a₁= a₂) и (b₁< b₂)).

Занумеруем проигрышные пары, начиная с 0. Ваша задача: найти k-ю пару проигрышных куч.

Входные данные

В первой строке входного файла INTPUT.TXT находится число N, (1 ≤ N ≤ 1000) - количество тестов в файле. В следующих N строках содержатся числа k_i, (0 ≤ k_i ≤ 10⁹) порядковый номер пары проигрышных куч, которую требуется найти.

Выходные данные

В выходной файл OUTPUT.TXT выведите N пар чисел (a_ki, b_ki) по одной в каждой строке.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]