题目背景

译自 Potyczki Algorytmiczne 2016 R5 Pokrycia [A] (POK)。

题目描述

简单无向图 $G=(V,E)$ 的点覆盖是一个点集 $S\subseteq V$，使得 $\forall (u,v)\in E$，都有 $u\in S$ 或 $v\in S$。点覆盖 $S$ 的大小定义为 $|S|$。

给定点集 $V$ 和整数 $k$，求出有多少张以 $V$ 为点集的简单无向图 $G$ 的最小点覆盖大小为 $k$。

两张图 $G_1=(V,E_1)$ 和 $G_2=(V,E_2)$ 不同，当且仅当存在 $u,v\in V$，使得 $(u,v)$ 只属于 $E_1$ 或 $E_2$。

给定正整数 $n$，点集 $V=\{1,2,\ldots,n\}$。

由于答案可能很大，所以只需要输出答案模 $\textcolor{red}{\textbf{2}}$ 后的余数。

输入格式

本题单个测试点内有多组测试数据。

第一行一个正整数 $T$，表示测试数据组数。

接下来描述 $T$ 组测试数据：

每组测试数据只有一行两个整数 $n,k$，表示一次询问。$V=\{1,2,\ldots,n\}$。

输出格式

输出 $T$ 行，每行一个非负整数，表示答案模 $\textcolor{red}{\textbf{2}}$ 后的余数。

4
3 1
5 4
5 3
57 32

0
1
1
1

提示

样例解释

• 第一组测试数据中，$n=3,k=1$。符合条件的图要么只有一条边，要么有两条边，且这两条边共用一个顶点。不难验证，原始答案为 $6$。
• 第二组测试数据中，$n=5,k=4$。不难验证符合条件的图只有完全图。

数据范围

• $1\le T\le 2^{14}$；
• $1\le n\lt 2^{14}$；
• $0\le k\lt n$。