- Time limit:
- 1000 ms
- Memory limit:
- 256 MB

Mathematical calculation is no longer a problem because one particular professor has invented “Atomic Computer” that is 8,000,000,000 times faster than the normal computer.

This Atomic Computer store data in special kind of very expensive memory. This memory store information very similar to traditional binary computer. The only exception is that one bit in this memory can represent 3 different states. These 3 states represents value -1, 0 and 1 respectively. This professor use the amazing property of this memory to construct marvelous things. You, as a senior student, would like to do a senior project with him.

The professor has suggested basic usage of the Atomic Computer to you. You try to have the computer store a value 1 in the memory. You then realized that the computer might store the value 1 in various way, one possible way is as (1)_{2} and another possible way is (1)(-1)_{2}

Write a program that read an integer value that you want to store in the memory and a number of bits in the memory. Calculate the number of all possible ways to store that number in the Atomic Computer.

## Input

The first line of input contain one integer T that gives the number of test cases. For each test case, there will be one line of input containing two integer xi and yi where x_{i} is the integer value we want to store in the memory and y_{i} is the number of bits in the computer. (-2,000,000,000 ≤ x_{i} ≤ 2,000,000,000 and 1 ≤ y_{i} ≤ 20)

## Output

There will be T lines of output. The i^{th} line gives the number of all possible ways to store the integer x_{i} using y_{i} bits of memory.

**Editor: **

**Source: **
ACM ICPC 2015 Thailand Local Central Group B