정점 덮개

무방향 단순 그래프 $G = (V, E)$의 정점 덮개는 모든 간선 $(u, v) \in E$에 대해 $u \in S$ 또는 $v \in S$가 성립하는 부분집합 $S \subseteq V$이다. 정점 덮개 $S$의 크기 $a$는 $|S|$로 정의한다.

정점이 $n$개인 단순 그래프 중 가장 작은 정점 덮개의 크기가 정확히 $k$인 그래프의 개수를 구하라.

두 그래프 $G\_1 = (V, E\_1)$과 $G\_2 = (V, E\_2)$는 두 정점 $u, v \in V$ ($u\neq v$)가 존재하여 간선 $(u, v)$가 $E\_1$, $E\_2$ 중 정확히 하나에만 속할 때 서로 다른 그래프로 본다.

답이 매우 클 수 있으므로, 답을 2로 나눈 나머지만 출력하면 된다.

첫 줄에 질의의 개수 $q$ ($1 \le q \le 2^{8}$)가 주어진다. 이후 $q$개의 줄에 각각 두 정수 $n_i$, $k_i$ ($1 \le n_i < 2^{8}$, $0 \le k_i < n_i$)가 주어진다. $n_i$는 그래프 $G$의 정점 수($|V|=n_i$)이고, $k_i$는 가장 작은 정점 덮개의 원하는 크기이다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답인 $0$ 또는 $1$을 출력한다.

첫 번째 질의에서 $V$의 크기는 $3$이다. 최소 정점 덮개의 크기가 $1$인 단순 그래프는 간선이 한 개 또는 두 개인 그래프뿐이며, 모두 6개이다.

두 번째 질의에서 정점이 $5$개인 그래프의 최소 정점 덮개 크기가 $4$라면, 그 그래프는 반드시 완전 그래프(clique)이다.