SP14905 ZIGZAG2 - Zig when you zag

我们称一个数列是「锯齿形」的，如果任意三个连续的元素既不构成非递增序列，也不构成非递减序列。具体而言，对于所有 $i = 1, 2, \ldots, k-2$，满足要么 $x(i+1) < x(i), x(i+2)$，要么 $x(i+1) > x(i), x(i+2)$。 现在，给定两个数列 $a(1), a(2), \ldots, a(n)$ 和 $b(1), b(2), \ldots, b(m)$。你的任务是计算它们的最长公共锯齿形子序列的长度。换句话说，需要从这两个数列中删除一些元素，使剩下的子序列不仅相同，还要保持为锯齿形。如果为了实现这一目标最少需要删除 $k$ 个元素，那么你应输出的答案是 $m + n - 2k$。

第一行输入一个整数 $t$，表示测试用例的数量。每个测试用例包含以下几行： - 第一行为一个整数 $n$，表示数列 $a$ 的长度。 - 第二行为数列 $a$ 的元素，包含 $n$ 个整数。 - 第三行为一个整数 $m$，表示数列 $b$ 的长度。 - 第四行为数列 $b$ 的元素，包含 $m$ 个整数。

对于每个测试用例，输出一行，表示数列 $a$ 和 $b$ 的最长公共锯齿形子序列的长度。

1 ≤ t ≤ 100，1 ≤ n, m ≤ 100，1 ≤ a(i), b(i) ≤ 1000。 **本翻译由 AI 自动生成**