사라진 순열

꼬마 토마토는 $1$부터 $n$까지의 수를 한 번씩 늘어놓은 순열 $P$를 칠판에 적어 둔다. 날마다 $P$의 수 몇 개를 서로 바꿔 새 순열 $P'$를 만들고, $P'$의 가장 긴 증가 부분 수열(LIS)을 찾는다. 언젠가 LIS를 더 빠르게 계산하는 방법을 찾아내리라 믿기 때문이다.

지진이 난 어느 날, 칠판에 적힌 수 가운데 몇 개가 떨어져 나갔다. 떨어진 수를 빈자리에 모두 되돌려 놓되 어느 자리에 놓을지는 토마토가 고른다. 이렇게 복원한 순열의 LIS 길이는 최대 얼마인가?

증가 부분 수열은 왼쪽에서 오른쪽으로 읽을 때 값이 계속 커지는 부분 수열이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 100$).

각 테스트 케이스의 첫째 줄에는 순열의 길이 $n$이 주어진다 ($1 \le n \le 10^5$). 둘째 줄에는 일부가 빠진 순열 $a_1, a_2, \dots, a_n$이 주어진다. $a_i = 0$은 원래 $i$번째 자리에 있던 수가 떨어졌다는 뜻이다.

입력은 항상 올바르다. $0$이 아닌 값은 서로 다르고 모두 $1$ 이상 $n$ 이하이며, 떨어진 수는 순열에 나타나지 않은 수와 정확히 일치한다. 입력 전체의 크기는 10MB 미만이다.

각 테스트 케이스마다 복원한 순열의 LIS 길이가 최대 얼마인지 한 줄에 출력한다.