새로운 복권 게임

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트

시간 제한: 60초. 1 ≤ A ≤ 1000. 1 ≤ B ≤ 1000. 1 ≤ K ≤ 1000.

큰 데이터 세트

시간 제한: 120초. 1 ≤ A ≤ $10^{9}$. 1 ≤ B ≤ $10^{9}$. 1 ≤ K ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에는 각각 세 수 A B K가 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 기계들이 생성하여 Catalina를 당첨자로 만들 수 있는 순서쌍의 수이다.

첫 번째 테스트 케이스에서 기존 기계와 새 기계가 각각 생성하여 그녀를 당첨자로 만들 수 있는 10개의 순서쌍은 다음과 같다: <0,0>, <0,1>, <0,2>, <0,3>, <1,0>, <1,1>, <1,2>, <1,3>, <2,0> 그리고 <2,1>. <0,1>는 <1,0>와 같지 않다는 점에 유의하라. 또한 순서쌍 <2, 2>는 기계들이 생성할 수 있지만, (2 AND 2) = 2이고 그녀는 수 0와 1만 구매했으므로 Catalina를 당첨자로 만들지는 못한다.