Binary Sum Tree Verification

You are given a binary tree represented in level order as a string of space-separated tokens. Each token represents a node's value, and the character N represents a null (absent) node. The tree is said to satisfy the Binary Sum Tree property if for every non-null node that has both a left and right child, the node's value is equal to the sum of the values of its left and right children. Note that if a node does not have both children (i.e. it is a leaf or has only one child), it does not need to satisfy this property.

For example, consider the tree represented by the tokens:

1 2 3 N N 2 1

The root node 1 has two children 2 and 3, but 1 is not equal to 2+3, so the property is violated.

Your task is to process multiple test cases. For each test case, determine if the given binary tree satisfies the Binary Sum Tree property.

inputFormat

The first line of input contains an integer T, the number of test cases. Each of the next T lines contains a space-separated string representing a binary tree in level order. The character 'N' denotes a null node.

outputFormat

For each test case, print a line in the format "Case #i: ", where is either "Yes" if the tree satisfies the Binary Sum Tree property or "No" otherwise. Cases are numbered starting from 1.## sample

1
1 2 3 N N 2 1

Case #1: No