

NANDTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 685 Accepted Submission(s): 246 Problem Description Xiaoqiang entered the ¡°shortest code¡± challenge organized by some selfclaimed astrologists. He was given a boolean function taking n inputs (in C++): bool f(bool x1, bool x2, bool x3){ //your code goes here //return something } All possible inputs and expected outputs of this function have been revealed: Xiaoqiang¡¯s code must be like: bool a = NAND(b, c); where ¡°a¡± is a newly defined variable,¡°b¡± and ¡°c¡± can be a constant (0/1) or a function parameter (x1/x2/x3) or a previously defined variable. NAND is the ¡°notand¡± function: NAND(b, c)=!(b&&c) Because NAND is universal, Xiaoqiang knew that he could implement any boolean function he liked. Also, at the end of the code there should be a return statement: return y; where y can be a constant or a function parameter or a previously defined variable. After staring at the function for a while, Xiaoqiang came up with the answer: bool a = NAND(x1, x2); bool b = NAND(x2, x3); bool y = NAND(a, b); return y; Xiaoqiang wants to make sure that his solution is the shortest possible. Can you help him? Input The first line contains an integer T (T ¡Ü 20) denoting the number of the test cases. For each test case, there is one line containing 8 characters encoding the truth table of the function. Output For each test case, output a single line containing the minimum number of lines Xiaoqiang has to write. Sample Input
Sample Output
Hint Due to the small input domain, you can solve all the cases on your computer and submit a program with a table of all the answers. Source  
