We define the T. M. sequence $\{T_n\}$ as a boolean sequence of the following form:

• $T_0 = 0$;
• $T_{2n} = T_n$;
• $T_{2n+1} = 1 - T_n$.

Here we provide the first few terms of the T. M. sequence: $01101001100101101001011001101001 \dots$.

The T. M. sequence is an infinite sequence, and it has many contiguous subsequences. For example, $0$, $1$, $10100$, $10011$, and $011001$ are all its contiguous subsequences, while $111$ and $1000$ are not.

Given a boolean sequence (a $01$ string) $S$ and a non-negative integer $k$, count how many contiguous subsequences $T$ of the T. M. sequence satisfy:

• $S$ is a prefix of $T$;
• $T$ is formed by appending exactly $k$ terms to the right of $S$.

Input

The first line contains an integer $T$, representing the total number of test cases.

Following this, there are $T$ lines, each containing a $01$ string $S$ (representing a boolean sequence) and a non-negative integer $k$ for each test case.

Output

For each test case, output a single line containing an integer representing the number of contiguous subsequences that satisfy the conditions. Since the value can be very large, output the result modulo $10^9 + 9$.

Examples

Input 1

5
1001 3
11001 10
00111 10
0011 20
0 100

Output 1

3
4
0
6
164

Subtasks

• Subtask 1: (20 points) $1 \le T \le 100$, the length of the given boolean sequence does not exceed $100$, and $0 \le k \le 100$.
• Subtask 2: (20 points) $1 \le T \le 100$, the length of the given boolean sequence does not exceed $100$, and $0 \le k \le 50000$.
• Subtask 3: (60 points) $1 \le T \le 100$, the length of the given boolean sequence does not exceed $100$, and $0 \le k \le 10^{18}$.