Xổ số đang thay đổi! Trước đây, Xổ số sử dụng một máy để tạo ra một số trúng thưởng ngẫu nhiên. Nhưng do các vấn đề gian lận, Xổ số đã quyết định thêm một máy nữa. Số trúng thưởng mới sẽ là kết quả của phép toán bitwise-AND giữa hai số ngẫu nhiên được tạo ra bởi hai máy.

Để tìm bitwise-AND của \(X\) và \(Y\), hãy viết cả hai ở dạng nhị phân; khi đó một bit trong kết quả nhị phân là \(1\) nếu các bit tương ứng của \(X\) và \(Y\) đều là \(1\), và bằng \(0\) nếu ngược lại. Trong hầu hết các ngôn ngữ lập trình, phép bitwise-AND của \(X\) và \(Y\) được viết là X & Y.

Ví dụ:

• Máy cũ tạo ra số \(7 = 0111_2\).
• Máy mới tạo ra số \(11 = 1011_2\).
• Số trúng thưởng sẽ là \((7 \text{ AND } 11) = (0111_2 \text{ AND } 1011_2) = 0011_2 = 3\).

Với biện pháp này, Xổ số hy vọng sẽ giảm bớt các trường hợp khiếu nại gian lận, nhưng không may một nhân viên từ công ty Xổ số đã rò rỉ thông tin sau: máy cũ sẽ luôn tạo ra một số nguyên không âm nhỏ hơn \(A\) và máy mới sẽ luôn tạo ra một số nguyên không âm nhỏ hơn \(B\).

Catalina muốn thắng giải xổ số này và để thử vận may, cô ấy quyết định mua tất cả các số nguyên không âm nhỏ hơn \(K\).

Cho \(A\), \(B\) và \(K\), Catalina muốn biết có bao nhiêu cách khác nhau mà các máy có thể tạo ra một cặp số để giúp cô ấy trở thành người chiến thắng.

Bạn có thể giúp cô ấy không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa ba số \(A\), \(B\) và \(K\).

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng cặp số khả thi mà các máy có thể tạo ra để Catalina thắng cuộc.

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Small dataset:

  • \(1 \le A \le 1000\).
  • \(1 \le B \le 1000\).
  • \(1 \le K \le 1000\).

  • Large dataset:

  • \(1 \le A \le 10^9\).

  • \(1 \le B \le 10^9\).
  • \(1 \le K \le 10^9\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
3 4 2
4 5 2
7 8 5
45 56 35
103 143 88

Case #1: 10
Case #2: 16
Case #3: 52
Case #4: 2411
Case #5: 14377

Nguồn

Google Code Jam 2014, Vòng 1B, bài New Lottery Game.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.