<reponame>aadhityasw/Competitive-Programs
def recurse(root) :
    if root is None :
        return (None, None, 0)
    
    if root.left is None and root.right is None :
        return (root.data, root.data, 1)
    
    if root.left and root.right :
        left = False
        left_part = recurse(root.left)
        (l1, r1, s1) = left_part
        if r1 is not None and r1 < root.data :
            left = True
        
        right = False
        right_part = recurse(root.right)
        (l2, r2, s2) = right_part
        if l2 is not None and l2 > root.data :
            right = True
        
        if left and right :
            return (l1, r2, s1+s2+1)
        return (None, None, max(s1, s2))
    
    if root.left :
        left_part = recurse(root.left)
        (l1, r1, s1) = left_part
        if r1 is not None and r1 < root.data :
            return (l1, root.data, s1+1)
        return (None, None, s1)
    
    if root.right :
        right_part = recurse(root.right)
        (l2, r2, s2) = right_part
        if l2 is not None and l2 > root.data :
            return (root.data, r2, s2+1)
        return (None, None, s2)



# Return the size of the largest sub-tree which is also a BST
def largestBst(root):
    
    _, _, size = recurse(root)
    return size




import sys
sys.setrecursionlimit(1000000)

from collections import deque

# Tree Node
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None

# Function to Build Tree
def buildTree(s):
    # Corner Case
    if (len(s) == 0 or s[0] == "N"):
        return None

    # Creating list of strings from input
    # string after spliting by space
    ip = list(map(str, s.split()))

    # Create the root of the tree
    root = Node(int(ip[0]))
    size = 0
    q = deque()

    # Push the root to the queue
    q.append(root)
    size = size + 1

    # Starting from the second element
    i = 1
    while size > 0 and i < len(ip):
        # Get and remove the front of the queue
        currNode = q[0]
        q.popleft()
        size = size - 1

        # Get the current node's value from the string
        currVal = ip[i]

        # If the left child is not null
        if (currVal != "N"):
            # Create the left child for the current node
            currNode.left = Node(int(currVal))

            # Push it to the queue
            q.append(currNode.left)
            size = size + 1
        # For the right child
        i = i + 1
        if (i >= len(ip)):
            break
        currVal = ip[i]

        # If the right child is not null
        if (currVal != "N"):
            # Create the right child for the current node
            currNode.right = Node(int(currVal))

            # Push it to the queue
            q.append(currNode.right)
            size = size + 1
        i = i + 1
    return root



if __name__ == "__main__":
    t = int(input())
    for _ in range(0, t):
        s = input()

        root = buildTree(s)

        print(largestBst(root))

def recurse(root) :
    if root is None :
        return (None, None, 0)
    
    if root.left is None and root.right is None :
        return (root.data, root.data, 1)
    
    if root.left and root.right :
        left = False
        left_part = recurse(root.left)
        (l1, r1, s1) = left_part
        if r1 is not None and r1 < root.data :
            left = True
        
        right = False
        right_part = recurse(root.right)
        (l2, r2, s2) = right_part
        if l2 is not None and l2 > root.data :
            right = True
        
        if left and right :
            return (l1, r2, s1+s2+1)
        return (None, None, max(s1, s2))
    
    if root.left :
        left_part = recurse(root.left)
        (l1, r1, s1) = left_part
        if r1 is not None and r1 < root.data :
            return (l1, root.data, s1+1)
        return (None, None, s1)
    
    if root.right :
        right_part = recurse(root.right)
        (l2, r2, s2) = right_part
        if l2 is not None and l2 > root.data :
            return (root.data, r2, s2+1)
        return (None, None, s2)



# Return the size of the largest sub-tree which is also a BST
def largestBst(root):
    
    _, _, size = recurse(root)
    return size




import sys
sys.setrecursionlimit(1000000)

from collections import deque

# Tree Node
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None

# Function to Build Tree
def buildTree(s):
    # Corner Case
    if (len(s) == 0 or s[0] == "N"):
        return None

    # Creating list of strings from input
    # string after spliting by space
    ip = list(map(str, s.split()))

    # Create the root of the tree
    root = Node(int(ip[0]))
    size = 0
    q = deque()

    # Push the root to the queue
    q.append(root)
    size = size + 1

    # Starting from the second element
    i = 1
    while size > 0 and i < len(ip):
        # Get and remove the front of the queue
        currNode = q[0]
        q.popleft()
        size = size - 1

        # Get the current node's value from the string
        currVal = ip[i]

        # If the left child is not null
        if (currVal != "N"):
            # Create the left child for the current node
            currNode.left = Node(int(currVal))

            # Push it to the queue
            q.append(currNode.left)
            size = size + 1
        # For the right child
        i = i + 1
        if (i >= len(ip)):
            break
        currVal = ip[i]

        # If the right child is not null
        if (currVal != "N"):
            # Create the right child for the current node
            currNode.right = Node(int(currVal))

            # Push it to the queue
            q.append(currNode.right)
            size = size + 1
        i = i + 1
    return root



if __name__ == "__main__":
    t = int(input())
    for _ in range(0, t):
        s = input()

        root = buildTree(s)

        print(largestBst(root))
# Return the size of the largest sub-tree which is also a BST # Tree Node # Function to Build Tree # Corner Case # Creating list of strings from input # string after spliting by space # Create the root of the tree # Push the root to the queue # Starting from the second element # Get and remove the front of the queue # Get the current node's value from the string # If the left child is not null # Create the left child for the current node # Push it to the queue # For the right child # If the right child is not null # Create the right child for the current node # Push it to the queue