input: p/2.

spec: exists X, Y p(X, Y) <-> exists X q(X).