평화의 게임

밥은 아주 특별한 준비가 필요한 새 마술을 배웠다. 이 마술을 완성하면 세계에 평화가 오지만, 실패하면 세계가 파괴된다.

준비 과정은 이렇다. 통이 두 개 있고, 처음에 한쪽은 비어 있으며 다른 쪽에는 구슬이 $X$개 들어 있다. 밥에게는 구슬 복제 기계가 있다. 이 기계는 구슬이 더 많은 통의 구슬을 복제한 다음, 복제한 구슬을 반대쪽 통에 붓는다. 예를 들어 두 통에 구슬이 7개와 4개 있으면 복제 후에는 7개와 11개가 된다. 기계는 이 복제를 정확히 $M$번 수행한다.

그런데 기계에 결함이 있다. 복제를 $N$번 ($N \le M$) 수행한 직후, 기계는 구슬이 더 많은 통에 구슬 $Y$개를 더 넣는다. 그 뒤 남은 복제를 정확히 $M - N$번 이어서 수행한다.

복제 도중 두 통의 구슬 수가 같으면 둘 중 어느 쪽이든 구슬이 더 많은 통으로 볼 수 있다.

밥의 친구 앨리스는 기계를 고치는 방법을 안다고 한다. 기계가 동작을 모두 마친 뒤 두 통에 든 구슬 수의 최대공약수를 구하기만 하면 된다. 밥을 도와 세계를 구하라.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 1000$)가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다.

각 테스트 케이스는 한 줄이며, 공백 하나로 구분된 정수 네 개 $X$, $N$, $Y$, $M$이 주어진다. $1 \le X, Y \le 1000$, $0 \le N \le 70$, $N \le M \le 100000$이다.

각 테스트 케이스마다 한 줄에 Case n: g 형식으로 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호이고, $g$는 기계가 동작을 마친 뒤 두 통에 든 구슬 수의 최대공약수이다.

$X = 4$, $N = 3$, $Y = 6$, $M = 5$인 경우 두 통의 구슬 수는 단계마다 $(4, 0)$, $(4, 4)$, $(4, 8)$, $(12, 8)$, $(18, 8)$, $(18, 26)$, $(44, 26)$으로 바뀐다. 44와 26의 최대공약수는 2이다.