import sys
import heapq

def main():
    try:
        input = sys.stdin.read
        data = input().split()
        index = 0
        testcases = int(data[index])
        index += 1
        results = []

        for _ in range(testcases):
            siz = int(data[index])
            ops = int(data[index + 1])
            word = data[index + 2]
            index += 3
            
            max_heap = []
            curr = 0
            
            for c in word:
                if c == '1':
                    curr += 1
                else:
                    if curr != 0:
                        heapq.heappush(max_heap, -curr)  # Use negative values for max heap
                    curr = 0
            
            if curr != 0:
                heapq.heappush(max_heap, -curr)
            
            while len(max_heap) > 1 and ops > 0:
                first = -heapq.heappop(max_heap)
                second = -heapq.heappop(max_heap) if max_heap else 0
                heapq.heappush(max_heap, -(first + second))
                ops -= 1
            
            results.append(str(-max_heap[0]))
        
        sys.stdout.write("\n".join(results) + "\n")
    except Exception as e:
        sys.stderr.write(str(e) + "\n")
        sys.exit(1)

if __name__ == "__main__":
    main()