Description

Alice and Bob are playing a game with $n$ coins numbered from $1$ to $n$. Each coin has two sides, called heads and tails. Initially, some coins are heads up and some are tails up. Alice and Bob alternate performing flip operations on these coins, and Alice always moves first.

Specifically, on each turn, the player may choose an index $x$ such that the coin $x$ is currently tails up. For the index $x$, we can always write $x = c \cdot 2^a \cdot 3^b$, where $a$ and $b$ are non-negative integers, and $c$ is a non-negative integer that is coprime to both $2$ and $3$. Then there are two choices:

• Choose integers $p, q$ satisfying $a \ge pq$, $p \ge 1$, and $1 \leq q \leq \text{MAXQ}$, then simultaneously flip all coins with indices $c \cdot 2^{a - pj} \cdot 3^b$, where $j = 0, 1, 2, \ldots, q$.

• Choose integers $p, q$ satisfying $b \ge pq$, $p \ge 1$, and $1 \leq q \leq \text{MAXQ}$, then simultaneously flip all coins with indices $c \cdot 2^a \cdot 3^{b - pj}$, where $j = 0, 1, 2, \ldots, q$.

It can be seen that the game cannot continue indefinitely. When a player cannot make a move as described above, they lose the game. As the first player, Alice wants to know beforehand whether she can win. She assumes that both she and Bob are perfectly rational, so during the game both will optimize their strategies and try to avoid losing.

Input Format

There are multiple test cases. The first line contains an integer $T$, the number of test cases. Then $T$ test cases follow.

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

The second line contains $n$ integers. The $i$-th number denotes the initial state of the $i$-th coin: $0$ means tails up, and $1$ means heads up.

Output Format

Output $T$ lines. For each test case, if Alice has a winning strategy as the first player, print win; otherwise print lose.

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

win
lose
win
lose
win
win

Hint

For $100\%$ of the testdata, $1 \le n \le 30000$, $1 \le \text{MAXQ} \le 20$, $T \le 100$.

Translated by ChatGPT 5