ZIGZAG2  Zig when you zag
We say that a sequence of numbers x(1),x(2),...,x(k) is zigzag if no three of its consecutive elements create a nonincreasing or nondecreasing sequence. More precisely, for all i=1,2,...,k2 either x(i+1)<x(i),x(i+2) or x(i+1)>x(i),x(i+2).
You are given two sequences of numbers a(1),a(2),...,a(n) and b(1),b(2),...,b(m). The problem is to compute the length of their longest common zigzag subsequence. In other words, you're going to delete elements from the two sequences so that they are equal, and so that they're a zigzag sequence. If the minimum number of elements required to do this is k then your answer is m+n2k.
Input
There is a single integer t (t≤100) on the first line of input. Then t test cases follow. Each of them consists of two lines. The first line contains the length of the first sequence n (1≤n≤2000) and n integers a(1),a(2),...,a(n). The second line contains the length of the second sequence m (1≤m≤2000) and m integers b(1),b(2),...,b(m). All a(i) and b(i) are from [10^{9},10^{9}]. (REPEAT: the first number on the line is not part of the sequence, it's the length of the sequence.)
Output
For each test case output one line containing the length of the longest common zigzag subsequence of a and b.
Example
Input: 2 5 1 2 5 4 3 5 4 1 2 5 3 3 1 2 1 2 1 1 Output: 3 2
hide comments
Sushovan Sen:
20161025 10:46:14
What is expected output for case:

Added by:  gawry 
Date:  20130510 
Time limit:  1s4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 