새 복권 게임 (Large)

복권 추첨 방식이 바뀐다. 예전에는 당첨 번호를 뽑는 기계가 하나뿐이었지만, 부정 행위가 이어지면서 복권 회사가 기계를 하나 더 놓기로 했다. 새 당첨 번호는 두 기계가 뽑은 두 난수의 비트 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 10^9$
• $1 \le B \le 10^9$
• $1 \le K \le 10^9$

각 테스트 케이스마다 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만 샀으므로 당첨되지 않는다.