Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3975
Sculpture Recovery

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.

Input

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.

Output

For each test case, output one integer, the largest possible volume of Kevin's new sculpture.

Sample Input

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

Sample Output

64
34

Source: ACM Collegiate Programming Contest 2017 (Hong Kong)
Submit    Status