小Hao的播放器

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

近来,小豪和小皓各获得了一个播放器,他们喜欢的不得了,天天见人便炫耀他们的播放器。
某一天,两个小 Hao 碰到了一起,发现对方也有一个播放器,便都心想得到对方的播放器,他们约定了一个游戏,如果谁赢了便可以得到对方的播放器,游戏规则如下:
小豪的播放器价值为 a,小皓的播放器价值为 b,将两个数中大的数,减去若干小的数的倍数,谁最终把一个数减为 0 的话就胜了(假设两个小 Hao 足够聪明)。

Input

输入数据有多组(数据组数不超过 1000),到 EOF 结束。

每组数据输入两个数 a, b (1 <= a, b <= 10^15),分别代表小豪的播放器的价值和小皓的播放器的价值,小豪先手。

Output

每组输入输出两行,第一行输出 "Case X:",X 代表第几组数据,第二行输出获胜者,若小豪获胜,则输出 "UMR",若小皓获胜则输出 "Have to give up",每组最后额外输出一行空行。

Sample Input

34 12
15 24

Sample Output

Case 1:
UMR

Case 2:
Have to give up

Hint

Source

【2017年寒假集训 结训赛1】C~K