Description

lsq’s deck has no Jokers and contains a total of $n$ cards. Since wzt is obsessed with exponentiation, he first proposed drawing $a^2$ cards each time (here “^” denotes exponentiation). lsq found that boring, so they changed the rule to drawing $a^k$ cards each time, where $k$ is a non-negative integer freely chosen by the player on their turn. lsq starts first, and the two players take turns drawing cards according to the rule. Whoever draws the last card wins.

Since they have plenty of time, lsq and wzt will play $q$ games in total, each with different $a$ and $n$. wzt banged out some code and can compute the winning strategy once $a$ and $n$ are fixed. After seeing your “operations,” lsq hopes you can also write a program to determine whether he can win given $a$ and $n$. Since lsq knows how to play optimally, you do not need to output the specific moves.

Note: In this problem, both players always choose a winning move whenever one exists.

Here $k$ is a non-negative integer that the player drawing the cards can decide on each turn. You can refer to the sample below for understanding.

Input Format

The first line contains one integer $q$, indicating there are $q$ games.
The next $q$ lines each contain two integers $a$, $n$, as defined above.

Output Format

Output $q$ lines.
If lsq can win, output "lsq Win".
If wzt can win, output "wzt Win".

3
2 5
2 9
3 9

lsq Win
wzt Win
lsq Win

Hint

Constraints:

• For 30% of the testdata, $q \le 30$, $a \le 30$, $n \le 10^8$.
• For 50% of the testdata, $q \le 50$, $a \le 30$, $n \le 10^{12}$.
• For 100% of the testdata, $q \le 50000$, $a \le 20000$, $n \le 10^{500}$.

Explanation for Sample 1:

• Query 1: lsq is guaranteed to win. lsq first draws $2^1 = 2$. Afterwards, no matter whether wzt draws $2^1 = 2$ or $2^0 = 1$, lsq can take all the remaining cards. Other draw orders are similar (just a different order).
• Query 2: wzt is guaranteed to win. If lsq first draws $2^0 = 1$, then wzt draws $2^3 = 8$. If lsq first draws $2^1 = 2$, then wzt draws $2^2 = 4$. Afterwards, no matter whether lsq draws $2^1 = 2$ or $2^0 = 1$, wzt can take all the remaining cards. Other draw orders are similar (just a different order).
• Query 3: lsq is guaranteed to win; he only needs to take $3^2 = 9$.

By Broadway

Translated by ChatGPT 5