Normal Form

Time limit1sMemory limit128 MB

Summary

Evaluate a fully parenthesized AND/OR tree where odd levels are AND and even levels are OR, for several long test cases.

Level: Medium5 of 10
Topics: Tree, Implementation, Recursion, String
Solved: No attempts yet

Problem

Every boolean expression can be written in Disjunctive Normal Form (DNF) or Conjunctive Normal Form (CNF). In this problem a DNF is one or more CNF expressions joined by OR, and a CNF is one or more DNF expressions joined by AND.

An AND/OR tree represents such a DNF or CNF boolean expression as a tree. Because DNF and CNF contain each other as subexpressions, knowing only the level of a subtree is enough to tell whether that subtree is an AND tree or an OR tree.

Levels are numbered from the top: the root is level 1, and the level increases by 1 for each step down. For example, the expression $(A \lor (B \land C)) \land (D \lor E)$ forms a tree whose level 1 (the root) and level 3 are AND trees while level 2 is an OR tree. In other words, odd levels are AND trees and even levels are OR trees.

Given an AND/OR tree, write a program that computes the value of the expression.

Input

The input consists of several test cases. Each test case is a single line no longer than 32,000 characters.

Each tree is given in the following format.

(E1 E2 ... En)

Here $n > 0$ always holds, and each $E_i$ is either the literal T (true), the literal F (false), or a subexpression (subtree) given in the same format.

The top of the tree (level 1, the root) is an AND tree. The last line of the input is (), which marks the end of the input.

Output

For each test case, print one line in the following format.

k. E

Here $k$ is the test case number (starting from 1) and $E$ is the value of the given expression, either true or false.

Examples1

Example 1

Input

((F(TF))(TF))
(TFT)
((TFT)T)
()

Expected output

1. false
2. false
3. true