Bob the Penguin recently stole a huge wooden board of width W and height H from Barr the Bear without him noticing. He divided the board into W*H cells, with the lower left corner having the coordinate of (1,1) and the upper-right corner having the coordinate of (W+1,H+1).
Feeling happy about himself, he randomly drilled 2*N holes along the width of the wooden board with his tough beak. However, he is not random enough, so there is a certain order in the points he drilled. More precisely, N of the holes lie on height 1 and the remaining N holes lie on height H.
After drilling holes, Bob's beak hurts, so he decided to try something else instead. He paired the 2*N points into N distinct pairs, where each point on row 1 is paired with a point on row H. Each pair is represented as P(A,B), which means point (A,1) and point (B,H) are paired together.
Then he wants to connect each pair of points with some colourful electric wires. Due to his poor eyesight, he cannot differentiate which points are connected together if wires of the same colour intersect. In order words, if P(A,B) and P(C,D) are connected with wires of the same colour, then the wires cannot intersect each other. For example, suppose we have two pairs P(1,2) and P(2,1). Then these two pairs will cross each other when connected with a wire. Therefore, the colour of the wires used to connect these two pairs must be different.
Bob the Penguin does not have wires, so he decides to steal the wires from Barr the Bear again. However, he decides to steal wires such that the number of different colours is minimal (That way, Barr the Bear will not get suspicious). However, he was recently exempted from taking the Common Test, so he had not been studying and was very rusty in his mathematical skills. Can you help him figure out what is the minimal number of colours needed?
Subtask 1 (40%): N ≤ 15.
Subtask 2 (30%): N ≤ 5,000.
Subtask 3 (30%): No Additional Constraints
Subtask 4 (0%): Sample Testcases
2 1 1 3 4
2 1 2 2 1