WFF 'N PROOF

Time limit1sMemory limit128 MB

Summary

Given counts of logic symbols, find the maximum length of a well-formed formula that can be built from a subset of them.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Implementation, Math
Solved: No attempts yet

Problem

WFF 'N PROOF is a logic game played with dice. Each die has six faces representing some subset of the possible symbols K, A, N, C, E, p, q, r, s, t. A well-formed formula (WFF) is any string of these symbols obeying the following rules:

p, q, r, s, and t are WFFs.
If w is a WFF, then Nw is a WFF.
If w and x are WFFs, then Kwx, Awx, Cwx, and Ewx are WFFs.

The meaning of a WFF is defined as follows:

p, q, r, s, and t are logical variables that may take on the value 0 (false) or 1 (true).
K, A, N, C, E mean and, or, not, implies, and equals as defined in the truth table below.

Definitions of K, A, N, C, and E
`w x`	`Kwx`	`Awx`	`Nw`	`Cwx`	`Ewx`
`1 1`	`1`	`1`	`0`	`1`	`1`
`1 0`	`0`	`1`	`0`	`0`	`0`
`0 1`	`0`	`1`	`1`	`1`	`0`
`0 0`	`0`	`0`	`1`	`1`	`1`

Given a collection of symbols resulting from throwing a set of dice, determine the length of the longest WFF that can be formed using some subset of those symbols.

Input

The input consists of several test cases. Each test case is a single line containing a string of between 1 and 100 of the characters K, A, N, C, E, p, q, r, s, t. A line containing a single 0 follows the last test case.

Output

For each test case, output a single line containing the length of the longest WFF that can be formed using some subset of the letters in the string. If no WFF can be constructed, output a line containing no WFF possible.

Examples1

Example 1
Input
```
qKpNq
KKN
0
```
Expected output
```
4
no WFF possible
```