Республиканская олимпиада по информатике 2014 год, Усть-Каменогорск

Задача B. Мансур побеждает Александра

Ограничение по времени:

2 секунды

Ограничение по памяти:

128 мегабайт

Задана игра на кучках камней. Ход игрока заключается в том, что он может взять произвольное количество камней из одной кучки, либо поровну из всех. Игроки чередуют ходы. Проигрывает тот, кто не может сделать ход. Мансур играет в эту игру с Александром. На столе лежат две кучки камней, в первой $a$, во второй $b$ камней. Первым ходит Мансур. Мансур понял, что если он может проиграть в заданную игру, он может своим ходом добавить третью кучку камней так, чтобы гарантированно победить. Если Мансур добавляет третью кучку, то ход переходит к Александру и далее игра идет только на трех кучках. Теперь перед ним встала задача, может ли он выиграть в эту игру или ему нужно первым ходом добавить третью кучку, тогда какого она должна быть размера? Помогите Мансуру. Мансур и Александр опытные ACMщики, поэтому можете считать, что они всегда ходят оптимально.

Формат входного файла

В первой строке входных данных задано одно целое число $1 \le T \le 100000$ — количество тестов. В следующих $T$ строках заданы тесты: два целых числа $a$ и $b$, разделенных одним пробелом.

Формат выходного файла

Выведите $T$ строк, ``MANSUR''\ если Мансур побеждает в изначальной игре, либо число $x$, если Мансуру нужно добавить кучку из $x$ камней чтобы победить. Если существует несколько ответов выведите любой.

Примеры:

Вход

5
1 1
1 2
3 3
3 5
9 24

Ответ

MANSUR
3
MANSUR
6
MANSUR

Замечание

Подзадача 1 — 21 балл $1 \le a,b \le 100$ Подзадача 2 — 23 балла $1 \le a,b \le 10000$ Подзадача 3 — 27 баллов $1 \le a,b \le 1000000$ Подзадача 4 — 29 баллов $1 \le a,b \le 10000000$