Республиканская олимпиада по информатике 2014 года за 10 класс | Казахстанские олимпиады

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

Ограничение по времени Ограничение по памяти
2 секунды 128 мегабайт

Задана игра на кучках камней. Ход игрока заключается в том, что он может взять произвольное количество камней из одной кучки, либо поровну из всех. Игроки чередуют ходы. Проигрывает тот, кто не может сделать ход.

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

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

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

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

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

Примеры

Вход

5
1 1
1 2
3 3
3 5
9 24

Выход

MANSUR
3
MANSUR
6
MANSUR