Permutacje

Kapitan Mambeks tworzy nowe szyfry permutacyjne. Przy tworzeniu szyfrów ważną rolę odgrywają ciągi rosnące. Dla każdej permutacji kapitan musi wyznaczyć długość najdłuższego ciągu rosnącego, a następnie liczbę elementów permutacji, które należą do co najmniej jednego z rosnących podciągów o takiej długości.

Dane wejściowe:

W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych n (0 ≤ n ≤ 20). W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. W każdym zestawie znajduje się opis permutacji. W pierwszym wierszu znajduje się długość permutacji k (1 ≤ k ≤ 100000). W kolejnych wierszach znajduje się k różnych liczb m (1 ≤ m ≤ 100000) - elementów permutacji.

Dane wyjściowe:

Dla każdego zestawu danych wejściowych program ma wypisać jeden wiersz zawierający liczbę elementów permutacji, które należą do co najmniej jednego z najdłuższych rosnących podciągów w permutacji.

Przykładowe dane wejściowe:

2
5
2 
1 
4 
5 
3
3
2 
3 
1
	

Przykładowe dane wyjściowe:

4
2