hackercupai/hackercup huggingface dataset:
Andy has no time for ores, he's just here for the `AND`s.

Andy has \(N\) pairs of integers, with each integer given in binary as a bitstring. The \(i\)th pair consists of bitstrings \(A_i\) and \(B_i\). No bitstring has leading zeros (except for the bitstring `"0"` itself).

Andy may choose at most \(K\) of these pairs for swapping. For each chosen pair \(i\), he'll swap its bitstrings \(A_i\) and \(B_i\).

After all of these swaps, he'll compute \(X\) as the bitwise `AND` of the \(N\) bitstrings \(A_{1..N}\), and \(Y\) as the bitwise `AND` of the \(N\) bitstrings \(B_{1..N}\), and finally add \(X\) and \(Y\) together. What's the maximum sum of \(X + Y\) that Andy can achieve?

Note that:

- The integer value of a bitstring \(S\) is equal to \(S_1 * 2^{|S|-1} + S_2 * 2^{|S|-2} + ... + S_{|S|} * 2^0\).
- The bitwise `AND` of a set of bitstrings \(S\) is a bitstring \(V\) such that, if leading zeros were appended to bitstrings in \(S\) until they all had the same length, then \(V\) also has that same length, with \(V_i\) equal to `1` if and only if all bitstrings in \(S\) have a `1` at index \(i\).

# Constraints

\(1 \le T \le 90\)
\(1 \le N \le 2{,}000{,}000\)
\(0 \le K \le N\)
\(0 \le A_{i,j}, B_{i,j} \le 1\)

The total length of all bitstrings \(A_{1..N}\) and \(B_{1..N}\) is at most \(4{,}000{,}000\).
The total length of all bitstrings across all test cases is at most \(10{,}000{,}000\).

# Input

Input begins with an integer \(T\), the number of test cases. For each test case, there is first a line containing \(2\) space-separated integers, \(N\) and \(K\). Then, \(N\) lines follow, the \(i\)th of which contains \(2\) space-separated bitstrings, \(A_i\) and \(B_i\).

# Output

For the \(i\)th test case, print a line containing *"Case #i: "* followed by a single bitstring, the maximum achievable sum of bitstring `AND`s, with no leading zeros (unless the bitstring is ``"0"``).

# Sample Explanation

In the first case, \(X = 1011011_2 \,(91_{10})\), \(Y = 101101_2 \,(45_{10})\), and \(X + Y = 10001000_2 \,(136_{10})\).

In the second case, no swaps are allowed, so we must have \(X = 1011011_2\) `AND` \(0_2 = 0_2\) and \(Y = 0_2 \) `AND` \(101101_2 = 0_2\).

In the third case, one option is to swap \(A_1\) and \(B_1\). This yields \(X = 0_2\) `AND` \(0_2 = 0_2\) and \(Y = 1011011_2\) `AND` \(101101_2 = 1001_2\).

In the fourth case, one option is to swap \(A_1\) and \(B_1\) as well as \(A_3\) and \(B_3\), resulting in \(X = 111_2 \,(7_{10})\), \(Y = 1_2 \,(1_{10})\), and \(X + Y = 1000_2 \,(8_{10})\).