Problem description

Ostatnio krasnoludkowi bliźniacy Zgapuś i Ściąguś pisali w szkole test z matematyki, który, jak twierdzili, poszedł im dobrze. Ku zdziwieniu ich mamy obaj otrzymali ocenę niedostateczną z dopiskiem praca niesamodzielna. Oburzona krasnalka natychmiast poprosiła synów o pokazanie kart odpowiedzi, aby sprawdzić, czy nauczycielka miała rację.

Zasady testu były proste — uczniowie wpisywali rozwiązania kolejnych zadań, każde w osobnej kolumnie; każde rozwiązanie było pojedynczą liczbą całkowitą. Mama postanowiła porównać karty obu krasnoludków kolumna po kolumnie i sprawdzić, w ilu miejscach wpisy synów różnią się od siebie.

Bracia nie chcieli przyznać się do współpracy podczas testu, więc postanowili zmodyfikować swoje karty odpowiedzi tak, aby wyglądały na możliwie najbardziej różne. Mama nie wie, ile było zadań na sprawdzianie, dlatego każdy z nich może wyciąć pewien początkowy fragment oraz pewien końcowy fragment swojej karty (fragmenty mogą być także puste). Zmodyfikowane karty odpowiedzi powinny być równej długości, gdyż różna liczba zadań na tym samym teście mogłaby wzbudzić podejrzenia.

Niestety, szybko okazało się, że znalezienie takich fragmentów, które różnią się na jak największej liczbie pozycji, wcale nie jest łatwiejsze od samego testu z matematyki. Bliźniaki nie poradziły sobie z tym problemem i ostatecznie dostały szlaban na komputer.

Pomóż bliźniakom: dla każdego sprawdzianu wyznacz maksymalną liczbę kolumn, na których mogą się różnić zmodyfikowane karty po wycięciu początkowych i końcowych fragmentów.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna T oznaczająca liczbę przypadków testowych. Opis każdego przypadku testowego składa się z trzech wierszy.

W pierwszym wierszu opisu przypadku testowego znajduje się jedna liczba naturalna N oznaczająca liczbę zadań na teście z matematyki.

W drugim i trzecim wierszu opisu przypadku testowego znajdują się ciągi A₁, A₂, …, A_N oraz B₁, B₂, …, B_N liczb całkowitych, opisujące odpowiednio odpowiedzi Zgapusia i Ściągusia.

Wyjście

Na wyjściu powinno znaleźć się T wierszy.

W i-tym z nich powinna znaleźć się odpowiedź do i-tego przypadku testowego, będąca jedną nieujemną liczbą całkowitą, oznaczającą maksymalną liczbę kolumn, na których mogą się różnić odpowiedzi bliźniaków po wycięciu początkowych i końcowych fragmentów.

Ograniczenia

1 ≤ T ≤ 10 000, 1 ≤ N ≤ 10 000,  − 10⁹ ≤ A_i, B_i ≤ 10⁹,
suma N po wszystkich przypadkach testowych nie przekracza 10 000.

Przykłady

3
7
1 1 1 2 2 2 1
1 1 1 1 2 2 1
6
-1 -4 2 -5 -2 10
4 4 2 2 -4 -8
3
1 1 1
1 1 1

4
5
0