Два стада на перевале
На перевале Тоо-Ашуу пастухи Азамат и Тилек коротают вечер за игрой. Перед ними две кучки камешков: в первой a камешков, во второй b. Игроки ходят по очереди, начинает Азамат. За ход можно:
- взять любое положительное число камешков из первой кучки;
- или взять любое положительное число камешков из второй кучки;
- или взять одно и то же положительное число камешков из обеих кучек сразу.
Кто не может сделать ход (обе кучки пусты), тот проиграл.
Ходы различаются кучкой (первая, вторая или обе) и числом взятых камешков. Для каждой из T позиций найдите количество выигрывающих ходов Азамата — таких, после которых Тилек при любой его игре проигрывает. Если таких ходов нет, Азамат проигрывает, и нужно вывести 0.
Входные данные
В первой строке — число T (1 ≤ T ≤ 10⁵). В каждой из следующих T строк — два целых числа a и b (0 ≤ a, b ≤ 10¹⁸).
Выходные данные
Для каждой позиции выведите количество выигрывающих ходов.
Пример 1
Вход:
5
3 3
2 2
3 5
10 6
0 7
Выход:
1
3
0
0
1
Пояснение
Проигрышные позиции (кто должен из них ходить, тот проигрывает при правильной игре соперника): (0, 0), (1, 2), (3, 5), (4, 7), (6, 10), … и симметричные им. Из (3, 3) выигрывает только ход «взять по 3 из обеих кучек» — в (0, 0). Из (2, 2) выигрывающих ходов три: в (0, 0), а также взять 1 камешек из одной из кучек — в (1, 2) или (2, 1).
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов a, b ≤ 150, ещё в 5 % тестов a, b ≤ 10⁶.
Подсказка
Теорема Битти: если α, β > 1 иррациональны и 1/α + 1/β = 1, то последовательности ⌊nα⌋ и ⌊nβ⌋ (n ≥ 1) вместе содержат каждое натуральное число ровно один раз.
Комментарии