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

(Мансұр Александрды жеңеді)

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

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$