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

[Ugur57]

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

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

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

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

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

(a1, b1) < (a2, b2), если (a1< a2) или ((a1= a2) и (b1< b2)).

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

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