Alice and Bob are playing a game with $n$ coins, numbered $1$ to $n$. Each coin has two sides: heads and tails. Initially, some coins are heads up and some are tails up. Alice and Bob take turns flipping these coins, with Alice going first.

Specifically, in each turn, a player chooses a coin with index $x$ that is currently tails up. For any index $x$, we can write $x = c \cdot 2^a \cdot 3^b$, where $a$ and $b$ are non-negative integers, and $c$ is a non-negative integer coprime to both $2$ and $3$. The player then has two choices:

1. Choose integers $p$ and $q$ such that $a \geq pq$, $p \geq 1$, and $1 \leq q \leq \text{MAXQ}$. Then, simultaneously flip all coins with indices $c \cdot 2^{a-pj} \cdot 3^b$ for $j = 0, 1, 2, \ldots, q$.
2. Choose integers $p$ and $q$ such that $b \geq pq$, $p \geq 1$, and $1 \leq q \leq \text{MAXQ}$. Then, simultaneously flip all coins with indices $c \cdot 2^a \cdot 3^{b-pj}$ for $j = 0, 1, 2, \ldots, q$.

It can be observed that this game cannot continue indefinitely. A player who cannot make a move loses the game. As the first player, Alice wants to know if she can win before the game starts. She knows that both she and Bob are perfectly rational, so both will optimize their strategies to ensure they remain in an undefeated position.

Input

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

For each test case, the first line contains two integers $n$ and $\text{MAXQ}$.

The second line contains $n$ integers, where the $i$-th integer represents the initial state of the $i$-th coin: 0 for tails up, and 1 for heads up.

Output

Output $T$ lines. For each test case, if Alice has a winning strategy, output "win"; otherwise, output "lose" (without quotes).

Examples

Input 1

6
16 14
1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1
16 14
0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1
16 11
0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1
16 12
1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0
16 4
1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0
16 20
0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0

Output 1

win
lose
win
lose
win
win

Subtasks

For $100 \%$ of the data, $1 \leq n \leq 30\,000, \ 1 \leq \text{MAXQ} \leq 20, \ t \leq 100$.