임원 회의

최근 한 투자 펀드가 당신을 고용했다. 뭔가 잘못되었다는 느낌이 곧바로 들었다. 특히 고객의 돈이 최고 점성술사가 신중하게 고른 두 회사에 투자되어 있을 때 그랬다.

안타깝게도 지난 $n$일 동안 주가는 (대체로) 떨어졌다. 사장이 긴급 회의를 소집했다.

"여러분, 상황은 다들 아시죠. 좋은 아이디어 있습니까?" 사장은 요점이 현실의 다른 차원에 있을 때조차 바로 본론으로 들어가는 좋은 습관이 있었다.

"주가가 계속 오르기만 하는 날들을 골라서, 그 날들의 회사 주가만 고객에게 보여주면 됩니다!" 이번 달의 최우수 사원 빌리가 나섰다.

"더 잘할 수 있습니다! 두 회사의 주가가 모두 증가하는 수열을 이루도록 날짜를 고르세요!" 선임 관리자 안나도 뒤처지지 않으려 했다.

"점성술사를 내보내고 제대로 된 조사를 하는 게 어떨까요?" 당신의 입에서 거의 무의식적으로 나온 말이었다. 두뇌와 성대가 당신의 동의 없이 먼저 움직인 것 같았다.

사장이 당신을 보았다. 진심으로 찬성하는 눈빛은 아니었다.

이제 당신에게는 멍이 들었고, 올라가야 할 계단도 많고, 할 일도 많다. 두 회사의 $n$일 연속 주가가 주어졌을 때, 두 가격 수열이 모두 (엄격하게) 증가하도록 날짜를 가장 많이 고르는 문제를 풀어라. 최대 날짜 수만 출력하면 된다.

첫 줄에 테스트 케이스의 개수 $z$가 주어진다. 각 테스트 케이스의 첫 줄에는 날짜 수 $n$($1 \leq n \leq 200\,000$)이 주어진다. 다음 두 줄 중 첫 줄에는 첫 번째 회사의 $n$일 동안의 주가가, 둘째 줄에는 두 번째 회사의 주가가 같은 형식으로 주어진다. 각 주가는 $10^9$를 넘지 않는 양의 정수이다. 모든 테스트 케이스의 날짜 수 합은 $2\,000\,000$을 넘지 않는다.

각 테스트 케이스마다 한 줄에 날짜 수의 최댓값을 정수 하나로 출력한다.