A vertex cover of an undirected simple graph $G = (V, E)$ is any subset of vertices $S \subseteq V$ such that for every edge $(u, v) \in E$, $u \in S$ or $v \in S$. The size of a vertex cover $S$ is the cardinality of the set $S$.

How many undirected simple graphs with a vertex set $V$ exist such that the minimum vertex cover size is exactly $k$? Two graphs $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ are considered 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, E_2$.

Since the number representing the answer to the above question could be very large, it is sufficient to provide the remainder of the division of this number by 2.

Input

The first line of the input contains a single integer $q$ ($1 \le q \le 2^{14}$), representing the number of queries.

The next $q$ lines contain descriptions of individual queries. The $i$-th of these lines contains the description of the $i$-th query: two integers $n_i$ and $k_i$ ($1 \le n_i < 2^{14}$, $0 \le k_i < n_i$), representing the number of vertices of the graph (i.e., $|V| = n_i$) and the given size of the minimum vertex cover, respectively.

Output

Output $q$ lines. The $i$-th line should contain the number 0 or 1 — the answer to the $i$-th query.

Examples

Input 1

4
3 1
5 4
5 3
57 32

Output 1

0
1
1
1

Note

• In the first query, the set $V$ has size 3. Simple graphs on the set $V$ with a minimum vertex cover of size 1 are exactly those graphs that have one or two edges. It is easy to verify that there are 6 such graphs.
• In the second case, only for the complete graph on a 5-element set $V$ does the minimum vertex cover have size 4.