Vertex covers

A vertex cover of an undirected simple graph $G = (V, E)$ is a subset $S \subseteq V$ such that for every $(u, v) \in E$ we have $u \in S$ or $v \in S$. The size $a$ of a vertex cover $S$ is $|S|$.

Find the number of simple graphs with $n$ vertices whose smallest vertex cover has size exactly $k$.

Two graphs $G\_1 = (V, E\_1)$ and $G\_2 = (V, E\_2)$ are different if and only if there exist two vertices $u, v \in V$ ($u\neq v$) such that the edge $(u, v)$ belongs to exactly one of the sets $E\_1$ and $E\_2$.

Since the answer can be very large, it suffices to print it modulo $2$.

The first line contains an integer $q$ ($1 \le q \le 2^{8}$), the number of queries. Each of the following $q$ lines contains two integers $n_i$ and $k_i$ ($1 \le n_i < 2^{8}$, $0 \le k_i < n_i$), where $n_i$ is the number of vertices of $G$ ($|V|=n_i$) and $k_i$ is the desired size of the smallest vertex cover.

Print $q$ lines. The $i$-th line contains the answer to the $i$-th query, either $0$ or $1$.

In the first query $V$ has size $3$. The simple graphs on $V$ whose smallest vertex cover has size $1$ are exactly the graphs with one or two edges. There are six of them.

In the second query, a graph on $5$ vertices whose smallest vertex cover has size $4$ must be a clique.