Given a Binary Tree of size N, find the size of the Largest Independent Set(LIS) in it. A subset of all tree nodes is an independent set if there is no edge between any two nodes of the subset. Your task is to complete the function LISS(), which finds the size of the Largest Independent Set.
For example:
Consider the following binary tree.The LIS is
LIS: [10, 40, 60, 70, 80]
Size: 5.
Example1:
Input:
10 20 30 40 50 N 60 N N 70 80
Output:
5
Explanation: LIS of the above 
tree will be [10,40, 60, 70,80]
Example 2:
Input: 
1 2 5 3 4 N 6
Output:
4
 
Constraints:
1<= Number of nodes <=500
Your Task:
You don't need to take input. Just complete the function LISS() that takes the root node as a parameter and returns the largest independent set.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3

def LISS(root):
    #code here

Solutions:
def LISS(root):

	def apply(root, choice):
		if not root:
			return 0
		if choice == 0:
			ans = max(1 + apply(root.left, 1) + apply(root.right, 1), apply(root.left, 0) + apply(root.right, 0))
		else:
			ans = apply(root.left, 0) + apply(root.right, 0)
		return ans
	return apply(root, 0)


def LISS(root):
	dp = {}

	def liss(root):
		if not root:
			return 0
		if root in dp:
			return dp[root]
		if root.left == None and root.right == None:
			return 1
		liss_excl = liss(root.left) + liss(root.right)
		liss_incl = 1
		if root.left:
			liss_incl = liss_incl + liss(root.left.left) + liss(root.left.right)
		if root.right:
			liss_incl = liss_incl + liss(root.right.right) + liss(root.right.left)
		dp[root] = max(liss_incl, liss_excl)
		return dp[root]
	return liss(root)


def LISS(root):
	dp = dict()

	def foo(dp, root, i):
		if not root:
			return 0
		if root in dp:
			if dp[root][i] != -1:
				return dp[root][i]
		else:
			dp[root] = [-1, -1]
		if i == 0:
			res = max(foo(dp, root.left, 1), foo(dp, root.left, 0)) + max(foo(dp, root.right, 1), foo(dp, root.right, 0))
		else:
			res = 1 + foo(dp, root.left, 0) + foo(dp, root.right, 0)
		dp[root][i] = res
		return res
	res = max(foo(dp, root, 1), foo(dp, root, 0))
	return res


def LISS(root):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return 1
	sizeincl = 1
	if root.left:
		sizeincl += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		sizeincl += LISS(root.right.left) + LISS(root.right.right)
	sizeexcl = LISS(root.left) + LISS(root.right)
	return max(sizeincl, sizeexcl)


def LISS(root):
	dp = dict()

	def findl(root, par):
		if root == None:
			return 0
		if (root, par) in dp:
			return dp[root, par]
		inc = 0
		if par != 1:
			inc = findl(root.left, 1)
			inc += findl(root.right, 1)
			inc += 1
		ninc = findl(root.left, 0)
		ninc += findl(root.right, 0)
		dp[root, par] = max(inc, ninc)
		return max(inc, ninc)
	return findl(root, 0)


def LISS(root):
	dp = dict()
	set_lis(root, dp)
	return traverse(root, dp)

def traverse(node, hasmap):
	if not node:
		return 0
	if hasmap[node] != -1:
		return hasmap[node]
	without = traverse(node.left, hasmap) + traverse(node.right, hasmap)
	with_ = 1
	if node.left:
		with_ += traverse(node.left.left, hasmap) + traverse(node.left.right, hasmap)
	if node.right:
		with_ += traverse(node.right.left, hasmap) + traverse(node.right.right, hasmap)
	hasmap[node] = max(with_, without)
	return hasmap[node]

def set_lis(node, dic):
	if node:
		dic[node] = -1
		set_lis(node.left, dic)
		set_lis(node.right, dic)
	return


def helper(root):
	if root == None:
		return 0
	pick = 0
	pick += 1
	if root.left != None:
		pick = pick + helper(root.left.left) + helper(root.left.right)
	if root.right != None:
		pick = pick + helper(root.right.left) + helper(root.right.right)
	notpick = 0
	notpick += helper(root.left) + helper(root.right)
	return max(pick, notpick)

def LISS(root):
	return helper(root)


def LISS(root):
	if root == None:
		return 0
	size_exc = LISS(root.left) + LISS(root.right)
	size_inc = 1
	if root.left:
		size_inc += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		size_inc += LISS(root.right.left) + LISS(root.right.right)
	return max(size_inc, size_exc)


def Postorder(root):
	if root == None:
		return [0, 0]
	l = Postorder(root.left)
	r = Postorder(root.right)
	if root.left == None and root.right == None:
		return [1, 0]
	ans = []
	val = 1 + l[1] + r[1]
	ans.append(1 + l[1] + r[1])
	max0 = max(l[0] + r[1], l[0] + r[0])
	max1 = max(l[1] + r[0], l[1] + r[1])
	ans.append(max(max0, max1))
	return ans

def LISS(root):
	ans = Postorder(root)
	return max(ans[0], ans[1])


def LISS(root):
	return helper(root)[0]

def helper(root):
	if root is None:
		return (0, True)
	if not root.left and (not root.right):
		return (1, False)
	(lsum, lflag) = helper(root.left)
	(rsum, rflag) = helper(root.right)
	return (lsum + rsum + 1, False) if lflag and rflag else (lsum + rsum, True)


from functools import lru_cache

def LISS(root):

	@lru_cache(None)
	def fun(node, f):
		if not node:
			return 0
		if f:
			return max(1 + fun(node.left, False) + fun(node.right, False), fun(node.left, True) + fun(node.right, True))
		return fun(node.left, True) + fun(node.right, True)
	return max(fun(root, True), fun(root, False))


def LISS(root):

	def manu(root, node, dp):
		if root is None:
			return 0
		(take, notake) = (0, 0)
		if node is None or (node.left != root and node.right != root):
			take = 1 + manu(root.left, root, dp) + manu(root.right, root, dp)
		notake = manu(root.left, node, dp) + manu(root.right, node, dp)
		return max(take, notake)
	dp = {}
	return manu(root, None, dp)


def LISS(root):

	def liss(node):
		if not node:
			return 0
		if not node.left and (not node.right):
			return 1
		if lookup.get(node, 0) != 0:
			return lookup[node]
		consider = 0
		notconsider = 0
		notconsider += liss(node.left) + liss(node.right)
		consider += 1
		if node.left:
			consider += liss(node.left.left) + liss(node.left.right)
		if node.right:
			consider += liss(node.right.left) + liss(node.right.right)
		lookup[node] = max(consider, notconsider)
		return lookup[node]
	lookup = {}
	ans = liss(root)
	return ans


def LISS(root):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return 1
	excludeNode = LISS(root.left) + LISS(root.right)
	includeNode = 1
	if root.left:
		includeNode += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		includeNode += LISS(root.right.left) + LISS(root.right.right)
	return max(excludeNode, includeNode)


def f(root, node):
	if root == None:
		return 0
	nottake = 0
	take = 0
	if node == None or (node.left != root and node.right != root):
		take = 1 + f(root.left, root) + f(root.right, root)
	nottake = f(root.left, node) + f(root.right, node)
	return max(nottake, take)

def LISS(root):
	return f(root, None)


def helper2(root, d):
	ans = 0
	if root.left:
		ans += helper(root.left.left, d) + helper(root.left.right, d)
	if root.right:
		ans += helper(root.right.left, d) + helper(root.right.right, d)
	return ans

def helper(root, d):
	if not root:
		return 0
	incl = 1 + helper2(root, d)
	excl = helper(root.left, d) + helper(root.right, d)
	d[root] = max(incl, excl)
	return d[root]

def LISS(root):
	d = {}
	return helper(root, d)


from collections import defaultdict

def solve(root):
	if root == None:
		return (0, 0)
	(a1, b1) = solve(root.left)
	(a2, b2) = solve(root.right)
	neta = 1 + b1 + b2
	netb = max(a1, b1) + max(a2, b2)
	return (neta, netb)

def LISS(root):
	return max(solve(root))


def __liss_helper(root):
	(take, not_take) = (1, 0)
	if root.left != None:
		(take_from_left, not_take_from_left, mx_sz_from_left) = __liss_helper(root.left)
		take += not_take_from_left
		not_take += max(not_take_from_left, take_from_left)
	if root.right != None:
		(take_from_right, not_take_from_right, mx_sz_from_right) = __liss_helper(root.right)
		take += not_take_from_right
		not_take += max(not_take_from_right, take_from_right)
	return (take, not_take, max(take, not_take))

def LISS(root):
	return __liss_helper(root)[2]


from collections import defaultdict

def solve(root, dp):
	if not root:
		return 0
	if dp[root] != 0:
		return dp[root]
	a = b = c = d = 0
	if root.left:
		a = solve(root.left.left, dp)
		b = solve(root.left.right, dp)
	if root.right:
		c = solve(root.right.left, dp)
		d = solve(root.right.right, dp)
	opt2 = solve(root.right, dp) + solve(root.left, dp)
	dp[root] = max(1 + a + b + c + d, opt2)
	return dp[root]

def LISS(root):
	dp = defaultdict(int)
	return solve(root, dp)


def solve(root):
	if not root:
		return 0
	a = b = c = d = 0
	if root.left:
		a = solve(root.left.left)
		b = solve(root.left.right)
	if root.right:
		c = solve(root.right.left)
		d = solve(root.right.right)
	opt2 = solve(root.right) + solve(root.left)
	return max(1 + a + b + c + d, opt2)

def LISS(root):
	return solve(root)


def answer(root, put):
	if root == None:
		return 0
	if put == 1:
		t1 = 1 + answer(root.left, 0) + answer(root.right, 0)
		t2 = answer(root.left, 1) + answer(root.right, 1)
		return max(t1, t2)
	else:
		return answer(root.left, 1) + answer(root.right, 1)

def LISS(root):
	return answer(root, 1)


def LISS(root):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		return 1
	choice1 = LISS(root.left) + LISS(root.right)
	choice2 = 1
	if root.left:
		choice2 += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		choice2 += LISS(root.right.left) + LISS(root.right.right)
	return max(choice1, choice2)


from collections import defaultdict

def LISS(root):
	h1 = defaultdict(int)
	h0 = defaultdict(int)
	h_0 = lambda node: h0[node] if node else 0
	h_1 = lambda node: h1[node] if node else 0

	def dfs(node):
		if node:
			dfs(node.left)
			dfs(node.right)
			h0[node] = h_1(node.left) + h_1(node.right)
			h1[node] = max(h0[node], h_0(node.left) + h_0(node.right) + 1)
	dfs(root)
	return max(h_0(root), h_1(root))


def LISS(root):
	if not root:
		return 0
	children = LISS(root.left) + LISS(root.right)
	grand_children = 1
	if root.left:
		grand_children += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		grand_children += LISS(root.right.left) + LISS(root.right.right)
	return max(children, grand_children)


def LISS(root):
	if not root:
		return 0
	size_excl = LISS(root.left) + LISS(root.right)
	size_incl = 1
	if root.left:
		size_incl += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		size_incl += LISS(root.right.left) + LISS(root.right.right)
	return max(size_incl, size_excl)


def LISS(root):

	def solve(x):
		if not x:
			return 0
		if hm.get(x, 0) != 0:
			return hm[x]
		if not x.left and (not x.right):
			hm[x] = 1
			return 1
		c = 1
		nonc = 0
		nonc += solve(x.left)
		nonc += solve(x.right)
		if x.left:
			c += solve(x.left.left)
			c += solve(x.left.right)
		if x.right:
			c += solve(x.right.left)
			c += solve(x.right.right)
		hm[x] = max(c, nonc)
		return hm[x]
	hm = dict()
	return solve(root)


def LISS(root):
	return liss(root)

def liss(root):
	if not root:
		return 0
	sum_child = liss(root.left) + liss(root.right)
	sum_gchild = 1
	if root.left:
		sum_gchild += liss(root.left.left) + liss(root.left.right)
	if root.right:
		sum_gchild += liss(root.right.left) + liss(root.right.right)
	return max(sum_child, sum_gchild)


def liss(root):
	if root == None:
		return 0
	if hasattr(root, 'liss'):
		if root.liss != 0:
			return root.liss
	if root.left == None and root.right == None:
		root.liss = 1
		return root.liss
	liss_excl = liss(root.left) + liss(root.right)
	liss_incl = 1
	if root.left != None:
		liss_incl += liss(root.left.left) + liss(root.left.right)
	if root.right != None:
		liss_incl += liss(root.right.left) + liss(root.right.right)
	root.liss = max(liss_excl, liss_incl)
	return root.liss

def LISS(root):
	return liss(root)


def f(node):
	if node is None:
		return 0
	excl = f(node.left) + f(node.right)
	incl = 1
	if node.left:
		incl += f(node.left.left) + f(node.left.right)
	if node.right:
		incl += f(node.right.left) + f(node.right.right)
	return max(incl, excl)

def LISS(root):
	return f(root)


from collections import defaultdict

def LISS(root):
	dp = defaultdict(list)

	def dfs(node):
		if node in dp:
			return dp[node]
		if node == None:
			return [0, 0]
		else:
			ret = [1 + dfs(node.left)[1] + dfs(node.right)[1], max(dfs(node.right)) + max(dfs(node.left))]
			dp[node] = ret
			return ret
	vals = dfs(root)
	return max(vals)


def LISS(root):
	return lisUtil(root, 1)

def lisUtil(root, flag):
	if root is None:
		return 0
	if flag == 1:
		return max(1 + lisUtil(root.left, 0) + lisUtil(root.right, 0), lisUtil(root.left, 1) + lisUtil(root.right, 1))
	return lisUtil(root.left, 1) + lisUtil(root.right, 1)


def LIS_util(root, memo):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return 1
	if root in memo:
		return memo[root]
	op1 = 1
	if root.left:
		op1 += LIS_util(root.left.left, memo) + LIS_util(root.left.right, memo)
	if root.right:
		op1 += LIS_util(root.right.left, memo) + LIS_util(root.right.right, memo)
	op2 = LIS_util(root.left, memo) + LIS_util(root.right, memo)
	memo[root] = max(op1, op2)
	return memo[root]

def LISS(root):
	memo = {}
	return LIS_util(root, memo)


def LISS(root):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		root.data = 1
		return 1
	root_ex = LISS(root.left) + LISS(root.right)
	root_in = 1
	if root.left:
		root_in += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		root_in += LISS(root.right.left) + LISS(root.right.right)
	root.data = max(root_in, root_ex)
	return root.data


def LISS(root):

	def solve(root):
		if root == None:
			return 0
		exclude_node = solve(root.left) + solve(root.right)
		include_node = 1
		if root.left != None:
			include_node += solve(root.left.left) + solve(root.left.right)
		if root.right != None:
			include_node += solve(root.right.left) + solve(root.right.right)
		return max(exclude_node, include_node)
	return solve(root)


def LISS(root):
	if not root:
		return 0
	g = 1
	s = 0
	if root.left:
		g += LISS(root.left.left)
		g += LISS(root.left.right)
		s += LISS(root.left)
	if root.right:
		g += LISS(root.right.left)
		g += LISS(root.right.right)
		s += LISS(root.right)
	return max(g, s)


def LISS(root):
	if not root:
		return 0
	inc = 0
	if root.left:
		inc += LISS(root.left.left)
		inc += LISS(root.left.right)
	if root.right:
		inc += LISS(root.right.left)
		inc += LISS(root.right.right)
	ex = LISS(root.right) + LISS(root.left)
	return max(inc + 1, ex)


def lis(root, include):
	if root is None:
		return 0
	inc = 0
	if include == True:
		inc = 1 + lis(root.left, False) + lis(root.right, False)
	exclude = lis(root.left, 1) + lis(root.right, 1)
	return max(inc, exclude)

def LISS(root):
	return lis(root, True)


def lis(root):
	if root is None:
		return 0
	includenode = 1
	if root.left:
		includenode += lis(root.left.left) + lis(root.left.right)
	if root.right:
		includenode += lis(root.right.left) + lis(root.right.right)
	excludenode = lis(root.left) + lis(root.right)
	return max(includenode, excludenode)

def LISS(root):
	return lis(root)


def lis(root):
	if root is None:
		return 0
	child = lis(root.left) + lis(root.right)
	grandchild = 1
	if root.left:
		grandchild += lis(root.left.left) + lis(root.left.right)
	if root.right:
		grandchild += lis(root.right.left) + lis(root.right.right)
	return max(grandchild, child)

def LISS(root):
	return lis(root)


def LISS(root):
	maxx = 0

	def recur(root):
		if root == None:
			return [0, 0]
		l = recur(root.left)
		r = recur(root.right)
		return [1 + l[1] + r[1], max(l) + max(r)]
	return max(recur(root))


def LISS(root):

	def f(root):
		if root == None:
			return 0
		inc = 1
		if root.left:
			inc += f(root.left.left) + f(root.left.right)
		if root.right:
			inc += f(root.right.right) + f(root.right.left)
		exc = 0
		exc = f(root.left) + f(root.right)
		return max(inc, exc)
	return f(root)


def LISS(root):
	if root == None:
		return 0
	donot = LISS(root.left) + LISS(root.right)
	inc = 1
	if root.left:
		inc += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		inc += LISS(root.right.left) + LISS(root.right.right)
	return max(donot, inc)


def LISS(root):
	ma = 0

	def f(r):
		if not r:
			return (0, 0)
		(la, lb) = f(r.left)
		(ra, rb) = f(r.right)
		nonlocal ma
		(a, b) = (lb + rb + 1, max(la, lb) + max(rb, ra))
		ma = max(ma, a, b)
		return (a, b)
	f(root)
	return ma


class node:

	def __init__(self, node):
		self.data = node.data if node is not None else None
		self.left = node.left if node is not None else None
		self.right = node.right if node is not None else None
		self.liss = 0

def findliss(root):
	if root is None:
		return 0
	if root.liss != 0:
		return root.liss
	if root.left == None and root.right == None:
		root.liss = 1
		return root.liss
	liss_excl = findliss(node(root.left)) + findliss(node(root.right))
	liss_incl = 1
	if root.left != None:
		liss_incl += findliss(node(root.left.left)) + findliss(node(root.left.right))
	if root.right != None:
		liss_incl += findliss(node(root.right.left)) + findliss(node(root.right.right))
	root.liss = max(liss_excl, liss_incl)
	return root.liss

def LISS(root):
	value1 = 1
	value2 = 0
	if root.right != None:
		value2 += LISS(root.right)
		if root.right.right != None:
			value1 += LISS(root.right.right)
		if root.right.left != None:
			value1 += LISS(root.right.left)
	if root.left != None:
		value2 += LISS(root.left)
		if root.left.right != None:
			value1 += LISS(root.left.right)
		if root.left.left != None:
			value1 += LISS(root.left.left)
	return max(value1, value2)


def solve(root, dp):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return 1
	if root in dp.keys():
		return dp[root]
	nottake = 0
	take = 0
	nottake = solve(root.left, dp) + solve(root.right, dp)
	take += 1
	if root.left is not None:
		take += solve(root.left.left, dp) + solve(root.left.right, dp)
	if root.right is not None:
		take += solve(root.right.left, dp) + solve(root.right.right, dp)
	dp[root] = max(take, nottake)
	return dp[root]

def LISS(root):
	dp = dict()
	return solve(root, dp)
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		print(LISS(root))


def LISS(root):
	count = 0

	def lis(node):
		nonlocal count
		if node == None:
			return (0, 0)
		left = lis(node.left)
		right = lis(node.right)
		wr = 1 + left[1] + right[1]
		wtr = max(left) + max(right)
		return [wr, wtr]
	return max(lis(root))
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		print(LISS(root))


def LISS(root):
	dp = {}

	def find(root, Take):
		if not root:
			return 0
		val = dp.get(root)
		if val != None:
			ans = val.get(Take)
			if ans != None:
				return ans
		if Take:
			ans = max(find(root.left, 0) + find(root.right, 0) + 1, find(root.left, 1) + find(root.right, 1))
		else:
			ans = find(root.left, 1) + find(root.right, 1)
		if val != None:
			dp[root][Take] = ans
		else:
			dp[root] = {Take: ans}
		return ans
	return max(find(root, 0), find(root, 1))
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		print(LISS(root))


def LISS(root):

	def solve(root):
		if root == None:
			return [0, 0]
		if root.left == None and root.right == None:
			return [1, 1]
		a = solve(root.left)
		b = solve(root.right)
		return [a[0] + b[0] + (1 - a[1]) * (1 - b[1]), (1 - a[1]) * (1 - b[1])]
	ans = solve(root)
	return ans[0]
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		print(LISS(root))


def LISS(root):

	def solve(root):
		if root == None:
			return [0, 0]
		if root.left == None and root.right == None:
			return [1, 1]
		a = solve(root.left)
		b = solve(root.right)
		return [a[0] + b[0] + (1 - a[1]) * (1 - b[1]), (1 - a[1]) * (1 - b[1])]
	ans = solve(root)
	return ans[0]


def LISS(root):
	dp = {}

	def sol(root, inc=1):
		if not root:
			return 0
		if (root, inc) in dp:
			return dp[root, inc]
		ans = 0
		if inc == 1:
			ans = max(ans, 1 + sol(root.left, 0) + sol(root.right, 0))
		ans = max(ans, sol(root.left, 1) + sol(root.right, 1))
		dp[root, inc] = ans
		return ans
	return sol(root, 1)


def LISS(root):

	def liss(root, hashmap):
		if root is None:
			return 0
		if root in hashmap:
			return hashmap[root]
		if root.left == None and root.right is None:
			hashmap[root] = 1
			return hashmap[root]
		incl = liss(root.left, hashmap) + liss(root.right, hashmap)
		excl = 1
		if root.left:
			excl += liss(root.left.left, hashmap)
			excl += liss(root.left.right, hashmap)
		if root.right:
			excl += liss(root.right.left, hashmap)
			excl += liss(root.right.right, hashmap)
		hashmap[root] = max(excl, incl)
		return hashmap[root]
	hashmap = {}
	liss(root, hashmap)
	return hashmap[root]


def LISS(root):
	if root == None:
		return 0
	excl = LISS(root.left) + LISS(root.right)
	incl = 1
	if root.left:
		incl += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		incl += LISS(root.right.left) + LISS(root.right.right)
	return max(excl, incl)


import queue

def LISS(root):

	def rec(nod):
		if nod.left is None and nod.right is None:
			return (1, 0)
		(ll, lp) = (0, 0)
		(rl, rp) = (0, 0)
		if nod.left:
			(ll, lp) = rec(nod.left)
		if nod.right:
			(rl, rp) = rec(nod.right)
		fir = max(1 + lp + rp, ll + rl)
		sec = ll + rl
		return (fir, sec)
	(x, y) = rec(root)
	return max(x, y)


def LISS(root):

	def cal(root, flag):
		if root == None:
			return 0
		if d[root][flag] != -1:
			return d[root][flag]
		if flag == 1:
			d[root][flag] = max(1 + cal(root.left, 0) + cal(root.right, 0), cal(root.left, 1) + cal(root.right, 1))
		else:
			d[root][flag] = cal(root.left, 1) + cal(root.right, 1)
		return d[root][flag]

	def inorder(root, d):
		if root != None:
			inorder(root.left, d)
			d[root] = [-1, -1]
			inorder(root.right, d)
	d = {}
	inorder(root, d)
	return cal(root, 1)


def LISS(root):
	if root is None:
		return 0
	else:
		exc = LISS(root.left) + LISS(root.right)
		inc = 1
		if root.left:
			inc += LISS(root.left.left) + LISS(root.left.right)
		if root.right:
			inc += LISS(root.right.left) + LISS(root.right.right)
		return max(inc, exc)


def LISS(root):

	def Helper(root):
		if root == None:
			return (0, 0)
		(lefti, leftni) = Helper(root.left)
		(righti, rightni) = Helper(root.right)
		return (1 + leftni + rightni, max(lefti + righti, leftni + righti, lefti + rightni, leftni + rightni))
	return max(Helper(root))


def util(root, accept):
	if root == None:
		return 0
	if (root, accept) not in util.mem:
		if accept == True:
			util.mem[root, accept] = max(1 + util(root.left, False) + util(root.right, False), util(root.left, True) + util(root.right, True))
		else:
			util.mem[root, accept] = util(root.left, True) + util(root.right, True)
	return util.mem[root, accept]

def LISS(root):
	util.mem = {}
	return max(util(root, True), util(root, False))


def util(root, accept):
	if root == None:
		return 0
	if accept == True:
		return max(1 + util(root.left, False) + util(root.right, False), util(root.left, True) + util(root.right, True))
	else:
		return util(root.left, True) + util(root.right, True)

def LISS(root):
	return max(util(root, True), util(root, False))


def helper(root):
	if root == None:
		return (0, 0)
	if root.left == None and root.right == None:
		return (1, 0)
	(child_l_in, child_l_ex) = helper(root.left)
	(child_r_in, child_r_ex) = helper(root.right)
	l = 1 + child_l_ex + child_r_ex
	r = max(child_l_in, child_l_ex) + max(child_r_in, child_r_ex)
	return (l, r)

def LISS(root):
	(l, r) = helper(root)
	return max(l, r)


def LISS(root):
	dic = {}

	def rec(root):
		if not root:
			return 0
		if root.data in dic:
			return dic[root]
		m1 = rec(root.right) + rec(root.left)
		m2 = 1
		if root.right:
			m2 += rec(root.right.right) + rec(root.right.left)
		if root.left:
			m2 += rec(root.left.right) + rec(root.left.left)
		dic[root] = max(m1, m2)
		return dic[root]
	return rec(root)


class Pair:

	def __init__(self):
		self.include = 0
		self.exclude = 0

def postorder(root):
	ans = Pair()
	if not root:
		return ans
	left = postorder(root.left)
	right = postorder(root.right)
	ans.include = 1 + left.exclude + right.exclude
	ans.exclude = max(left.exclude, left.include) + max(right.exclude, right.include)
	return ans

def LISS(root):
	ans = postorder(root)
	return max(ans.include, ans.exclude)


def LISS(root):
	if not root:
		return 0
	including = 1
	excluding = 0
	if root.left:
		including += LISS(root.left.left) + LISS(root.left.right)
		excluding += LISS(root.left)
	if root.right:
		including += LISS(root.right.left) + LISS(root.right.right)
		excluding += LISS(root.right)
	return max(excluding, including)


d = {}

def LISS(root):
	if root == None:
		return 0
	if root in d.keys():
		return d[root]
	exc = LISS(root.left) + LISS(root.right)
	inc = 1
	if root.left:
		inc += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		inc += LISS(root.right.right) + LISS(root.right.left)
	d[root] = max(inc, exc)
	return max(inc, exc)


def LISS(root):

	def dfs(root):
		if not root:
			return 0
		l = 0
		if root.left != None:
			l += LISS(root.left.left) + LISS(root.left.right)
		if root.right != None:
			l += LISS(root.right.left) + LISS(root.right.right)
		return max(1 + l, dfs(root.left) + dfs(root.right))
	return dfs(root)


def LISS(r):

	def recur(root):
		if not root:
			return (0, 0)
		(inc1, exc1) = recur(root.left)
		(inc2, exc2) = recur(root.right)
		inc = 1 + exc1 + exc2
		exc = max(inc1, exc1) + max(inc2, exc2)
		return (inc, exc)
	return max(recur(r))


def LISS(root):

	def divideNodes(root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 1
		lis_wo_node = divideNodes(root.left) + divideNodes(root.right)
		lis_w_node = 1
		if root.left:
			lis_w_node += divideNodes(root.left.left) + divideNodes(root.left.right)
		if root.right:
			lis_w_node += divideNodes(root.right.right) + divideNodes(root.right.left)
		return max(lis_w_node, lis_wo_node)
	return divideNodes(root)


def LISS(root):

	def helper(root):
		if not root:
			return 0
		a = 0
		b = 0
		if root.left:
			a = helper(root.left.left) + helper(root.left.right)
		if root.right:
			b = helper(root.right.left) + helper(root.right.right)
		c = helper(root.left) + helper(root.right)
		return max(a + b + 1, c)
	return helper(root)


def LISS(root):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		return 1
	use = 1
	if root.left:
		use += LISS(root.left.left) + LISS(root.left.right)
	if root.right:
		use += LISS(root.right.right) + LISS(root.right.left)
	return max(use, LISS(root.left) + LISS(root.right))


def helper(root, mem):
	if not root:
		return 0
	if root in mem:
		return mem[root]
	include = 1
	if root.left:
		include += helper(root.left.left, mem) + helper(root.left.right, mem)
	if root.right:
		include += helper(root.right.left, mem) + helper(root.right.right, mem)
	exclude = helper(root.left, mem) + helper(root.right, mem)
	mem[root] = max(exclude, include)
	return mem[root]

def LISS(root):
	return helper(root, {})


lisMap = {}

def LISS(root):
	global lisMap
	if root == None:
		return 0
	if root in lisMap:
		return lisMap[root]
	if root.left == None and root.right == None:
		lisMap[root] = 1
		return 1
	exc = LISS(root.left) + LISS(root.right)
	inc = 1
	if root.left != None:
		inc += LISS(root.left.left) + LISS(root.left.right)
	if root.right != None:
		inc += LISS(root.right.left) + LISS(root.right.right)
	lisMap[root] = max(inc, exc)
	return lisMap[root]


def LISS(root):
	dp = {}

	def find(x):
		if not x:
			return 0
		if x in dp:
			return dp[x]
		(t1, t2, t3, t4) = (0, 0, 0, 0)
		if x.left:
			(t1, t2) = (find(x.left.left), find(x.left.right))
		if x.right:
			(t3, t4) = (find(x.right.left), find(x.right.right))
		a = 1 + t1 + t2 + t3 + t4
		b = find(x.left) + find(x.right)
		dp[x] = max(a, b)
		return dp[x]
	return find(root)


def LISS(root):
	memo = {}

	def largest(node):
		if node == None:
			return 0
		exc = inc = 0
		if node.left:
			inc += largest(node.left.left) + largest(node.left.right)
		if node.right:
			inc += largest(node.right.left) + largest(node.right.right)
		exc = largest(node.left) + largest(node.right)
		memo[node] = max(inc + 1, exc + 1)
		return max(inc + 1, exc)
	return largest(root)