Background

The statement of this problem is highly ambiguous. Below is a comparison between the Luogu version and the Lanqiao Cup official website testdata:

• Luogu: resonance happens as long as the digits $0, 2, 4$ appear.
• Lanqiao Cup official website: resonance requires that the two numbers share a pair among $0, 2, 4$ in common.

Because the statement is ambiguous, the testdata of this problem is for reference only.

Problem Description

In the Lanqiao Kingdom, two wizards, Xiao Lan and Xiao Qiao, are responsible for maintaining the order of space and time. Each of them has $N$ rune stones. Every stone is carved with a numeric symbol between $1$ and $10^9$. Xiao Lan's stones are denoted as $s_1, s_2, \cdots, s_N$, and Xiao Qiao's are denoted as $t_1, t_2, \cdots, t_N$.

Their task is to travel through nodes in space-time using these rune stones. Each travel follows this rule: after Xiao Lan uses rune stone $s_i$ to reach a new node, Xiao Qiao must choose a rune stone with a larger index (that is, some $t_j$ with $j > i$) to go to the next node. Similarly, after Xiao Qiao arrives, Xiao Lan must choose a rune stone $s_k$ with index $k > j$ to continue the tour.

To travel successfully, the numeric symbols on two consecutively used rune stones must resonate. This resonance happens only when the numeric symbols contain at least one special element: Spark (digit $0$), Ripple (digit $2$), or Windwhisper (digit $4$). For example, in the symbol sequence $126, 552, 24, 4$, every pair of consecutive runes contains at least one resonance element, so it is a successful tour sequence. But $15, 51, 5$ does not work, because their resonance elements do not include any of Spark, Ripple, or Windwhisper.

Xiao Lan always starts first, using his rune stones to begin the tour.

Your task is to compute the maximum length of a space-time tour sequence that these two wizards can perform. Such a sequence has the form $s_{i_1}, t_{i_2}, s_{i_3}, t_{i_4}, \cdots$, where the indices satisfy $i_1 < i_2 < i_3 < i_4 < \cdots$, and every adjacent pair of rune stones in the sequence contains at least one resonance element.

Input Format

The first line contains an integer $N$, representing the number of rune stones each wizard has.

The second line contains $N$ integers $s_1, s_2, \cdots, s_N$, separated by spaces, representing the numeric symbols carved on Xiao Lan's rune stones.

The third line contains $N$ integers $t_1, t_2, \cdots, t_N$, separated by spaces, representing the numeric symbols carved on Xiao Qiao's rune stones.

Output Format

Output one line containing one integer, representing the maximum number of space-time tours Xiao Lan and Xiao Qiao can perform while following all rules.

5
126 393 581 42 44
204 990 240 46 52

4

Hint

For $30\%$ of the test cases, $1 \le N \le 10^3$, $1 \le s_i, t_i \le 10^5$.

For all test cases, $1 \le N \le 10^5$, $1 \le s_i, t_i \le 10^9$.

Sample Explanation

Here, digit $2$ serves as a resonance element connecting $s_1$ and $t_3$, and $s_4$ and $t_5$. Digits $2$ and $4$ serve as resonance elements connecting $t_3$ and $s_4$.

Translated by ChatGPT 5