let id x = x

let (>>=) l f = List.flatten (List.map f l)

type tree = False
          | True
          | Var of int
          | Neg of tree
          | Xor of tree * tree
          | And of tree * tree

let parse str =
  let rec loop i = match String.get str i with
      '0' -> (False, i + 1)
    | '1' -> (True, i + 1)
    | 'a' .. 'd' as c -> (Var (Char.code c - Char.code 'a'), i + 1)
    | '-' -> let (t, i) = loop (i + 1) in
             (Neg t, i)
    | '(' -> let (t1, j) = loop (i + 1) in
             let (t2, k) = loop (j + 1) in
             if String.get str j = '^' then
               (Xor (t1, t2), k + 1)
             else
               (And (t1, t2), k + 1)
    | _ -> raise (Failure "") in
  let (t, _) = loop 0 in
  t

let rec truth_table t =
  match t with
  | False -> 0
  | True -> 0xffff
  | Var 0 -> 0x5555
  | Var 1 -> 0x3333
  | Var 2 -> 0x0f0f
  | Var 3 -> 0x00ff
  | Neg t -> lnot (truth_table t) land 0xffff
  | Xor (t1, t2) -> truth_table t1 lxor truth_table t2
  | And (t1, t2) -> truth_table t1 land truth_table t2
  | _ -> raise (Failure "")

let all_patterns =
  let gen l t = (truth_table t, l) in
  let gen' (p1, l1) (p2, l2) =
    [(p1 land p2, l1 + l2 + 3); (p1 lxor p2, l1 + l2 + 3);
     (lnot (p1 land p2) land 0xffff, l1 + l2 + 4); (lnot (p1 lxor p2) land 0xffff, l1 + l2 + 4)] in
  let ps11 = List.map (gen 1) [False; True] in
  let ps12 = List.map (gen 1) [Var 0; Var 1; Var 2; Var 3] @
               List.map (gen 2) (List.map (fun t -> Neg t) [Var 0; Var 1; Var 2; Var 3]) in
  let ps2 = ps12 >>= (fun p1 ->
              ps12 >>= (fun p2 ->
                gen' p1 p2)) in
  let ps3 = ps12 >>= (fun p1 ->
              ps2 >>= (fun p2 ->
                gen' p1 p2)) in
  let ps41 = ps2 >>= (fun p1 ->
               ps2 >>= (fun p2 ->
                 gen' p1 p2)) in
  let ps42 = ps12 >>= (fun p1 ->
               ps3 >>= (fun p2 ->
                 gen' p1 p2)) in
  List.fold_left (fun l l' -> List.rev_append l' l) ps42 [ps41; ps3; ps2; ps12; ps11]

let rec loop () =
  let str = Scanf.scanf "%s\n" id in
  if str <> "." then
    let tt = truth_table (parse str) in
    let res = all_patterns
              |> List.filter (fun (p, _) -> p = tt)
              |> List.map snd
              |> List.fold_left min 100 in
    Printf.printf "%d\n" res;
    flush stdout;
    loop ()

let () = loop ()
