Problem: mr_x (2019 quals)

"There's nothing more important than x!", laughs Mr. X as he explains a
Boolean expression involving a variable x to you and your classmates. He can't
go 5 minutes teaching Boolean algebra without making at least one such
"joke"...

In Mr. X's class, you've been learning about single-variable Boolean
expressions, which are made up of the variable x (and its negation), Boolean
constants (True/False), and binary Boolean operators. A valid expression is a
string in one of the following two forms:

1) A single term, which is one of the following four characters:

  * "`x`": The variable x 
  * "`X`": The negation of the variable x 
  * "`0`": The constant False 
  * "`1`": The constant True 

2) A binary operator joining two valid expressions in the format
"`([expression][operator][expression])`", with the operator being one of the
following three characters:

  * "|": The OR operator (evaluating to True when at least one of its operands is True) 
  * "&": The AND operator (evaluating to True when both of its operands are True) 
  * "^": The XOR operator (evaluating to True when exactly one of its operands is True) 

For example, the following expressions are **valid**:

  * "`1`" 
  * "`(x^0)`" 
  * "`((X&0)|x)`" 

While the following expressions are **invalid**:

  * "`(1)`" 
  * "`x^0`" 
  * "`(X&0|x)`" 

An upcoming test will feature a valid expression **E** in the above format,
which must be evaluated for a certain value of x. However, you've been getting
tired of Mr. X and his lame jokes about the importance of x, so you're
planning on hacking into his test files and changing the expression so as to
make x irrelevant! In particular, you'd like to modify as few characters as
possible in **E** such that it ends up still being a valid expression, but
such that its overall value doesn't depend on the value of the variable x. You
may only change characters in-place into different characters — you may not
insert or delete characters.

For example, the expression "`(X|(0&x))`" evaluates to True if x is False, and
False if x is True. If it were to be changed into "`((X&0)&1)`" (by modifying
its 2nd, 3rd, 4th, 6th, 7th, and 8th characters), then it would evaluate to
False regardless of x's value. Though, it's also possible to make its value
independent of x by modifying fewer than 6 of its characters.

Given an expression **E**, what's the minimum number of characters which must
be modified? It's possible that no characters may need to be modified at all.

### Input

Input begins with an integer **T**, the number of tests. For each test, there
is a line containing the expression **E**.

### Output

For the _i_th test, print a line containing "Case #_i_: " followed by a single
integer, the minimum number of characters to modify in **E** such that the
result is a valid expression whose value doesn't depend on the value of x.

### Constraints

1 ≤ **T** ≤ 500  
1 ≤ |**E**| ≤ 300  

### Explanation of Sample

The first expression can, for example, be changed to "`1`" (and would then
always evaluate to True).

The second expression can be left unchanged (as it always evaluates to False).

The third expression can be left unchanged (as it always evaluates to True).

The fourth expression can, for example, be changed to "`((0^(X&X))|x)`" (and
would then always evaluate to True).



Sample input:
4
X
0
(x|1)
((1^(X&X))|x)


Sample output:
Case #1: 1
Case #2: 0
Case #3: 0
Case #4: 1



Code: // Mr. X
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

int Eval(int v1,char o,int v2)
{
		if (o=='|')
			return(v1|v2);
		if (o=='&')
			return(v1&v2);
	return(v1^v2);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int i,x,ss;
	char S[303],st[303];
	char res[2];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			scanf("%s",&S);
			// evaluate expression for x=0 and x=1
				Fox(x,2)
				{
					ss=0;
						Fox(i,strlen(S))
							if (S[i]==')')
							{
								ss-=3;
								st[ss-1]=Eval(st[ss]-'0',st[ss+1],st[ss+2]-'0')+'0';
							}
							else
							if (S[i]=='x')
								st[ss++]=x+'0';
							else
							if (S[i]=='X')
								st[ss++]=(1-x)+'0';
							else
								st[ss++]=S[i];
					res[x]=st[0];
				}
			// output
			printf("Case #%d: %d\n",t,(res[0]==res[1])?0:1);
		}
	return(0);
}