Day of the Programmer- HackerRank problem

 Binary String Battle

time limit per test

2 seconds

memory limit per test

256 megabytes

Alice and Bob are given a binary string s$s$ of length n$n$, and an integer k$k$ (1≤k<n$1\le k<n$).

Alice wins if she is able to transform all characters of s$s$ into zeroes. If Alice is unable to win in a finite number of moves, then Bob wins.

Alice and Bob take turns, with Alice going first.

• On Alice's turn, she may choose any subsequence∗${}^{\text{∗}}$ of length k$k$ in s$s$, then set all characters in that subsequence to zero.
• On Bob's turn, he may choose any substring†${}^{\text{†}}$ of length k$k$ in s$s$, then set all characters in that substring to one.

Note that Alice wins if the string consists of all zeros at any point during the game, including in between Alice's and Bob's turns.

Determine who wins with optimal play.

∗${}^{\text{∗}}$A subsequence of a string s$s$ is a set of characters in s$s$. Note that these characters do not have to be adjacent.

†${}^{\text{†}}$A substring of a string s$s$ is a contiguous group of characters in s$s$. Note that these characters must be adjacent.

Input

The first line contains an integer t$t$ (1≤t≤104$1\le t\le {10}^4$)  — the number of test cases.

The first line of each test case contains two integers n$n$ and k$k$ (2≤n≤2⋅105$2\le n\le 2\cdot {10}^5$, 1≤k<n$1\le k<n$).

The second line of each test case contains a binary string s$s$ of length n$n$.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, output on a single line "Alice" if Alice wins with optimal play, and "Bob" if Bob wins with optimal play.

You can output the answer in any case (upper or lower). For example, the strings "aLiCe", "alice", "ALICE", and "alICE" will be recognized as "Alice".

Example

Input

Copy

6
5 2
11011
7 4
1011011
6 1
010000
4 1
1111
8 3
10110110
6 4
111111

Output

Copy

Bob
Alice
Alice
Bob
Bob
Alice

Note

In the third sample, Alice can choose the subsequence consisting of s2$s_2$, turning s$s$ into 000000$000000$. Then she wins immediately.

In the fourth sample, it can be shown that there is no way for Alice to guarantee that she can turn s$s$ into 0000$0000$ within a finite number of moves.

Codeforce Problem - Binary String Battle solution

Codeforce Problem - Binary String Battle solution by java

Codeforce Problem - Binary String Battle solution by Python