문제

복권이 변하고 있습니다! 예전에 복권은 무작위로 당첨 숫자를 생성하는 기계를 활용했습니다. 하지만 꼼수 때문에, 복권 기금은 새로운 기계를 추가하기로 했습니다. 새로운 당첨 숫자는 두 기계에서 생성된 두 개의 무작위 숫자를 AND 비트 연산한 값이 될 것입니다. 

X와 Y의 AND 비트 연산 값을 찾기 위해서는, 우선 두 숫자를 이진수로 적습니다; 만약 X와 Y에 해당하는 비트가 모두 1이면 결과 값의 비트도 1, 그 외의 경우 비트는 0이 됩니다. 대부분의 프로그래밍 언어에서 AND 비트 연산은 X&Y로 표시합니다. 

예를 들어:

예전 기계가 숫자 7 = 0011을 생성한다고 가정하고,

새로운 기계가 숫자 11 = 1011을 생성한다고 가정하면,

당첨 숫자는 (7 AND 11) = (0111 AND 1011) = 0011 = 3이 될 것입니다.

이 방법을 이용해 복권 기금은 사기를 방지할 것을 기대했으나, 안타깝게도 복권 기금의 직원이 아래의 정보를 유출했습니다: 예전 기계는 언제나 A보다 작은 음이 아닌 정수를 생성하고 새 기계는 언제나 B보다 작은 음이 아닌 정수를 생성한다.

카탈리나는 복권에 당첨되고 싶어 K보다 작은 모든 음이 아닌 정수 값의 복권을 구매했습니다. 

A, B, K가 주어질 때, 카탈리나는 그녀를 당첨되게 해주는 숫자 쌍의 수를 알고 싶습니다.

그녀를 도와줄 수 있나요?

입력

첫 줄에 테스트 케이스의 수 T가 주어집니다. T개의 줄 각각에 세 숫자 A, B, K가 주어집니다.

제한

- 1 <= T <= 100

- 1 <= A <= 1000

- 1 <= B <= 1000

- 1 <= K <= 1000

출력

각 테스트 케이스에 대해, x는 (1부터 시작하는) 테스트 케이스의 번호를 나타내고 y는 카탈라니가 당첨되는 숫자 쌍의 수를 나타내는 "Case #x: y"를 한 줄에 출력합니다.