Time Limit: 2 Seconds
Memory Limit: 65536 KB
Kevin is an artist who creates 3-D sculptures. Whenever Kevin completes a sculpture, he will take digital pictures of the sculpture from the top view, front view, and left-side view, respectively. The pictures of the three views are black and white, with the background being white, and with the sculpture being black. Each of the three digital pictures contains several rows with each row having several pixels, where each pixel is a 1cm by 1cm square, represented by a binary number, equal to 0 if the pixel is white, and equal to 1 if the pixel is black.
Given the pictures of the three views of Kevin's new sculpture, your task is to recover the sculpture. Since there can be multiple possible sculptures with the same pictures of the three views, you need to find the one with the largest volume.
Figure 5. An illustrated example with three views and their digital pictures for a sculpture of a volume equal to 64.
The first line of the input contains the number of test cases T, and cases are separated by empty lines.
For each test case, its first line contains three integers a, b and h, where 1 ≤ a, b, h ≤ 200. It is followed by one b×a binary matrix, one h×a binary matrix, one h×b binary matrix, representing the digital pictures of the top view, the front view, and the left-side view of Kevin's sculpture respectively, where the three matrices are separated by empty lines.
For each test case, output one integer, the largest possible volume of Kevin's new sculpture.
2 4 4 6 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 0110 0110 0110 0110 1111 1111 2 4 7 11 11 11 11 10 01 11 11 11 11 11 0101 1111 1111 0111 0011 1111 0001