ZIGZAG2 - Zig when you zag

no tags 

We say that a sequence of numbers x(1), x(2) ... x(k) is zigzag if no three of its consecutive elements create a non-increasing or non-decreasing sequence. More precisely, for all i=1, 2 ... k-2 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+n-2k.

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 [-109, 109]. (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
miamimagna: 2024-11-03 19:48:42

am I the only one who can't decipher this question

amangoyal097: 2020-07-14 21:40:42

Try using two states of dp and the special cases:
1) ans is 0
2) ans is 2

Last edit: 2020-07-14 21:41:08
gauravsingh_: 2019-09-14 11:29:15

some important test cases:-
2
7 1 2 3 4 20 10 30
7 20 10 30 1 2 3 4
4 1 1 1 1
3 1 1 1

gauravsingh_: 2019-09-09 18:30:45

what's wrong in following approach?
1. find the lcs
2. find the length of longest zig-zag sub - sequence of lcs found in step(1)

Sushovan Sen: 2016-10-25 10:46:14

What is expected output for case:
1
5 4 5 5 6 8
5 5 4 4 3 2
Is it 4 OR 2?

Last edit: 2016-10-25 10:55:57

Added by:gawry
Date:2013-05-10
Time limit:1s-4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64