Given a binary tree containing one or more BSTs, find the size of the the largest BST subtree.

Examples

Note: The smallest answer would be 1. The largest answer would be n where the entire binary tree is a BST.

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has 2 lines:

• The first line contains an integer n denoting the number of nodes in the tree (including the NULL nodes).
• The second line contains n space-separated integers that will form the binary tree. The integers follow level order traversal of the tree where -1 indicates a NULL node.

Output Format

For each test case, the output has a single integer containing the size of the largest binary tree.

Sample Input

3
12
1 2 6 1 5 8 -1 -1 -1 4 -1 7
12
6 2 9 1 5 8 -1 -1 -1 4 -1 7
3
28 14 11

Expected Output

4
8
1

Constraints

1 <= T <= 10
1 <= n <= 104
1 <= node value <= 104