원자 컴퓨터

한 교수가 보통 컴퓨터보다 80억 배 빠른 원자 컴퓨터를 만들었다. 이 컴퓨터는 값을 특수한 메모리에 저장하는데, 이 메모리는 한 비트가 -1, 0, 1 세 가지 상태 중 하나를 나타낸다.

$y$비트 메모리에 저장된 비트를 앞에서부터 $d_{y-1}, d_{y-2}, \dots, d_1, d_0$이라고 하면, 메모리가 나타내는 값은 다음과 같다.

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

각 $d_i$는 -1, 0, 1 중 하나다. 예를 들어 $(1)(-1)(0)_2$은 $1 \cdot 4 + (-1) \cdot 2 + 0 \cdot 1 = 2$를 나타낸다. 비트 수는 항상 $y$로 고정이고, 앞쪽 비트가 0인 표현도 서로 다른 저장 방법으로 센다.

저장하려는 정수 $x$와 메모리의 비트 수 $y$가 주어질 때, $x$를 $y$비트에 저장하는 방법의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($T \ge 1$)

다음 $T$개 줄에 각각 두 정수 $x_i$와 $y_i$가 주어진다. $x_i$는 메모리에 저장하려는 값이고, $y_i$는 메모리의 비트 수다. ($-2000000000 \le x_i \le 2000000000$, $1 \le y_i \le 20$)

$T$개 줄을 출력한다. $i$번째 줄에는 $x_i$를 $y_i$비트에 저장하는 방법의 수를 출력한다.