새로운 복권 게임 (스몰)

복권 추첨 방식이 바뀐다. 지금까지는 당첨 번호를 뽑는 기계가 하나뿐이었는데, 조작이 드러나면서 기계를 하나 더 두기로 했다. 새 당첨 번호는 두 기계가 각각 만든 난수 두 개의 비트 AND 연산 결과다.

$X$와 $Y$의 비트 AND는 두 수를 이진수로 적은 뒤, 같은 자리의 비트가 둘 다 1이면 결과의 그 자리를 1로, 아니면 0으로 놓아 얻는다. 대부분의 프로그래밍 언어에서 이 연산은 X & Y로 쓴다.

예를 들어 예전 기계가 7 = 0111을 만들고 새 기계가 11 = 1011을 만들면, 당첨 번호는 (0111 AND 1011) = 0011 = 3이다.

복권 회사는 이 방식으로 부정 당첨을 줄이려 했지만, 직원 한 명이 정보를 흘렸다. 예전 기계는 항상 $A$보다 작은 음이 아닌 정수를 만들고, 새 기계는 항상 $B$보다 작은 음이 아닌 정수를 만든다는 것이다.

카탈리나는 이 복권에 당첨되고 싶어서 $K$보다 작은 음이 아닌 정수를 모두 샀다.

$A$, $B$, $K$가 주어질 때, 두 기계가 만들 수 있는 수의 쌍 가운데 카탈리나를 당첨시키는 쌍이 몇 가지인지 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에 각각 세 정수 $A$, $B$, $K$가 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 100$
• $1 \le A \le 1000$
• $1 \le B \le 1000$
• $1 \le K \le 1000$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 카탈리나를 당첨시키는 쌍의 개수다.

$A = 3$, $B = 4$, $K = 2$인 경우 카탈리나를 당첨시키는 쌍은 (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1)의 10가지다. 쌍의 앞쪽은 예전 기계가, 뒤쪽은 새 기계가 만든 수이므로 (0, 1)과 (1, 0)은 서로 다른 쌍이다. (2, 2)도 두 기계가 만들 수 있지만 (2 AND 2) = 2이고 카탈리나는 0과 1만 샀으므로 당첨되지 않는다.