Atomic Computer

A professor has built the Atomic Computer, which runs 8,000,000,000 times faster than a normal computer. It keeps values in a special memory where one bit represents one of three states, -1, 0 and 1.

Write the bits of a $y$ bit memory as $d_{y-1}, d_{y-2}, \dots, d_1, d_0$, starting from the front. The value held by the memory is

$\sum_{i=0}^{y-1} d_i \cdot 2^{i}$

Each $d_i$ is -1, 0 or 1. For example, $(1)(-1)(0)_2$ holds $1 \cdot 4 + (-1) \cdot 2 + 0 \cdot 1 = 2$. The number of bits is always exactly $y$, and a representation whose leading bits are 0 counts as its own way of storing the value.

Given an integer $x$ to store and the number of bits $y$, count the ways to store $x$ in $y$ bits.

The first line contains the number of test cases $T$. ($T \ge 1$)

Each of the next $T$ lines contains two integers $x_i$ and $y_i$, where $x_i$ is the value to store and $y_i$ is the number of bits. ($-2000000000 \le x_i \le 2000000000$, $1 \le y_i \le 20$)

Print $T$ lines. The $i$th line contains the number of ways to store $x_i$ in $y_i$ bits.