잭팟

빌은 슬롯머신으로 돈을 버는 완벽한 방법을 찾아냈습니다. 몇 달간의 연구 끝에 그는 마침내 슬롯머신이 작동하는 원리를 알아냈고, 이제 그 발견으로 이익을 낼 준비가 되었습니다.

먼저 게임을 소개합니다. 슬롯머신은 여러 개의 휠(보통 3개 또는 4개)로 이루어져 있으며, 각 휠에는 체리, 오렌지, 종 등 여러 기호가 그려져 있고 한 번에 하나의 기호만 보여 줍니다. 게임을 하려면 동전을 넣고 버튼을 누르며, 그러면 휠이 회전하기 시작합니다. 잠시 회전한 뒤 각 휠은 (무작위처럼 보이게) 어떤 기호에서 멈춥니다. 모든 휠이 같은 기호에서 멈추거나 특정한 조합을 이루면 플레이어가 이깁니다. 특히 모든 휠이 잭팟 기호에서 멈추는 조합을 '잭팟'이라 부르며, 이 조합이 나오면 평생 부자가 됩니다.

빌이 알아낸 사실은, 각 휠이 일정한 주기마다 잭팟 기호에서 멈춘다는 것이며 이 주기는 휠마다 크게 다릅니다. 또한 (공장을 몰래 살펴본 끝에) 새로 제조된 모든 슬롯머신은 출고 시 잭팟 조합을 보여 주는 상태로 배송되고, 뒷면에는 기계가 몇 번 플레이되었는지를 나타내는 카운터가 달려 있으며 이 카운터는 출고 시 0으로 설정된다는 것도 알아냈습니다.

이제 빌이 해야 할 일은, 한 기계가 잭팟 조합을 두 번 보여 주는 사이에 몇 번 플레이되어야 하는지를 계산하는 것입니다. 이 값을 '잭팟 주기'라고 부릅시다. 이는 기계가 공장을 떠난 뒤 처음 잭팟을 낼 때까지 플레이되어야 하는 횟수와 같습니다. 따라서 뒷면 카운터를 한 번 보기만 하면 빌은 그 기계가 곧 잭팟을 낼지 알 수 있습니다.

빌은 당신이 뛰어난 프로그래머라는 것을 알기에, 잭팟 주기를 계산하는 문제를 들고 찾아왔습니다. 각 기계에 대해 휠의 개수와, 각 휠에서 잭팟 기호가 나타나는 주기가 주어집니다.

첫 줄에 기계의 수 $n \le 20$ 이 주어집니다.

각 기계에 대해, 한 줄에 휠의 수 $w \le 5$ 가 주어지고, 그다음 줄에 각 휠의 주기 $p_1, \dots, p_w$ 가 공백으로 구분되어 주어집니다. 여기서 각 $p_k \le 1000$ 입니다.

각 기계마다 한 줄씩 그 기계의 잭팟 주기를 출력합니다. 단 그 값이 10억($10^9$) 이하인 경우에만 값을 출력하고, 그렇지 않으면 More than a billion. 을 출력합니다.