#pragma GCC optimize("O3") //コンパイラ最適化用 //#define _GLIBCXX_DEBUG //配列に[]でアクセス時のエラー表示 /* #region */ #define _USE_MATH_DEFINES #include //sort,二分探索,など #include //固定長bit集合 // #include // #include #include //assert(p)で,not pのときにエラー #include #include //実行時間計測 #include #include //pow,logなど #include //複素数 #include #include #include #include //sortのgreater #include //setprecision(浮動小数点の出力の誤差) #include // std::left, std::right #include //入出力 #include //集合演算(積集合,和集合,差集合など) #include #include //iota(整数列の生成),gcdとlcm,accumulate #include #include #include #include #include #include #include #include //pair #include using namespace std; typedef long long LL; typedef long double LD; #define ALL(x) x.begin(), x.end() const long long INF = numeric_limits::max() / 4; const int MOD = 1e9 + 7; // const int MOD=998244353; //略記 #define FF first #define SS second #define int long long #define stoi stoll #define LD long double #define PII pair #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(x) (int)((x).size()) #define VB vector #define VVB vector> #define VI vector #define VVI vector> #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define REPD(i, n) for (int i = (int)(n) - (int)1; i >= 0; i--) #define FOR(i, a, b) for (int i = a; i < (int)(b); i++) #define FORD(i, a, b) for (int i = (int)(b) - (int)1; i >= (int)a; i--) const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0}; const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int in() { int x; cin >> x; return x; } // https://qiita.com/Lily0727K/items/06cb1d6da8a436369eed#c%E3%81%A7%E3%81%AE%E5%AE%9F%E8%A3%85 void print() { cout << "\n"; } template void print(Head &&head, Tail &&...tail) { cout << head; if (sizeof...(tail) != 0) cout << " "; print(forward(tail)...); } template void print(vector &vec) { for (auto &a : vec) { cout << a; if (&a != &vec.back()) cout << " "; } cout << "\n"; } template void print(set &set) { for (auto &a : set) { cout << a << " "; } cout << "\n"; } template void print(vector> &df) { for (auto &vec : df) { print(vec); } } long long power(long long x, long long n) { // O(logn) // https://algo-logic.info/calc-pow/#toc_id_1_2 long long ret = 1; while (n > 0) { if (n & 1) ret *= x; // n の最下位bitが 1 ならば x^(2^i) をかける x *= x; n >>= 1; // n を1bit 左にずらす } return ret; } // @brief nCr. O(r log n)。あるいは前処理 O(n), 本処理 O(1)で求められる modint // の bc を検討。 int comb(int n, int r) { // https://www.geeksforgeeks.org/program-to-calculate-the-value-of-ncr-efficiently/ // p holds the value of n*(n-1)*(n-2)..., // k holds the value of r*(r-1)... long long p = 1, k = 1; // C(n, r) == C(n, n-r), // choosing the smaller value if (n - r < r) r = n - r; if (r != 0) { while (r) { p *= n; k *= r; // gcd of p, k long long m = __gcd(p, k); // dividing by gcd, to simplify // product division by their gcd // saves from the overflow p /= m; k /= m; n--; r--; } // k should be simplified to 1 // as C(n, r) is a natural number // (denominator should be 1 ) . } else p = 1; // if our approach is correct p = ans and k =1 return p; } // MOD void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; } template inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } // 負数も含む丸め long long ceildiv(long long a, long long b) { if (b < 0) a = -a, b = -b; if (a >= 0) return (a + b - 1) / b; else return a / b; } long long floordiv(long long a, long long b) { if (b < 0) a = -a, b = -b; if (a >= 0) return a / b; else return (a - b + 1) / b; } long long floorsqrt(long long x) { assert(x >= 0); long long ok = 0; long long ng = 1; while (ng * ng <= x) ng <<= 1; while (ng - ok > 1) { long long mid = (ng + ok) >> 1; if (mid * mid <= x) ok = mid; else ng = mid; } return ok; } // @brief a^n mod mod long long modpower(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // @brief s が c を含むか template bool contain(const std::string &s, const T &c) { return s.find(c) != std::string::npos; } __attribute__((constructor)) void faster_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } /* #endregion */ template struct RangeSet { private: const T TINF = std::numeric_limits::max() / 2; std::set> st; public: RangeSet() { st.emplace(-TINF, -TINF + 1); st.emplace(TINF, TINF + 1); } //[l, r) is covered? bool covered(const T l, const T r) { assert(l < r); auto itr = prev(st.lower_bound({l + 1, -TINF})); return itr->first <= l and r <= itr->second; } //[x, x + 1) is covered? bool covered(const T x) { return covered(x, x + 1); } // return section which covers[l, r) // if not exists, return[-TINF, -TINF) std::pair covered_by(const T l, const T r) { assert(l < r); auto itr = prev(st.lower_bound({l + 1, -TINF})); if (itr->first <= l and r <= itr->second) return *itr; return {-TINF, -TINF}; } // return section which covers[x, x + 1) // if not exists, return[-TINF, -TINF) std::pair covered_by(const T x) { return covered_by(x, x + 1); } // insert[l, r), and return increment T insert(T l, T r) { if (l >= r) return 0; auto itr = prev(st.lower_bound({l + 1, -TINF})); if (itr->first <= l and r <= itr->second) return T(0); T sum_erased = T(0); if (itr->first <= l and l <= itr->second) { l = itr->first; sum_erased += itr->second - itr->first; itr = st.erase(itr); } else itr = next(itr); while (r > itr->second) { sum_erased += itr->second - itr->first; itr = st.erase(itr); } if (itr->first <= r) { sum_erased += itr->second - itr->first; r = itr->second; st.erase(itr); } st.emplace(l, r); return r - l - sum_erased; } // insert[x, x + 1), and return increment T insert(const T x) { return insert(x, x + 1); } // erase [l, r), and return decrement T erase(const T l, const T r) { assert(l < r); auto itr = prev(st.lower_bound({l + 1, -TINF})); if (itr->first <= l and r <= itr->second) { if (itr->first < l) st.emplace(itr->first, l); if (r < itr->second) st.emplace(r, itr->second); st.erase(itr); return r - l; } T ret = T(0); if (itr->first <= l and l < itr->second) { ret += itr->second - l; if (itr->first < l) st.emplace(itr->first, l); itr = st.erase(itr); } else itr = next(itr); while (itr->second <= r) { ret += itr->second - itr->first; itr = st.erase(itr); } if (itr->first < r) { ret += r - itr->first; st.emplace(r, itr->second); st.erase(itr); } return ret; } // erase [x, x + 1), and return decrement T erase(const T x) { return erase(x, x + 1); } int size() { return (int)st.size() - 2; } // x 以上で区間に含まれていない最小の値を返す int mex(const T x = 0) { auto itr = prev(st.lower_bound({x + 1, -TINF})); if (itr->first <= x and x < itr->second) return itr->second; else return x; } // 点の数を返す T sum_all() const { T res = 0; for (auto &p : st) { if (std::abs(p.first) == TINF) continue; res += p.second - p.first; } return res; } std::set> get() const { std::set> res; for (auto &p : st) { if (std::abs(p.first) == TINF) continue; res.emplace(p.first, p.second); } return res; } void dump() const { std::cout << "Rangeset:"; for (auto &p : st) { if (std::abs(p.first) == TINF) continue; std::cout << "[" << p.first << "," << p.second << "),"; } std::cout << '\n'; } }; // cf. https://atcoder.jp/contests/arc112/submissions/20166587 // https://scrapbox.io/fukucchi/%E5%8C%BA%E9%96%93 /* int b, c; signed main() { cin >> b >> c; RangeSet rs; rs.insert(-b - (c - 1) / 2, -b + (c - 1) / 2 + 1); rs.insert(b - c / 2, b + (c - 2) / 2 + 1); rs.dump(); print(rs.sum_all()); print(rs.mex(10)); return 0; } */ int p; int get_grundy(int n, int k) { RangeSet rs; VI grundy(n, -1); VI cnt(max(n, k) + 10, 0); grundy[n - 1] = 0; // 負け確局面 cnt[grundy[n - 1]]++; rs.insert(grundy[n - 1], grundy[n - 1] + 1); FORD(ni, max(0LL, n - 1 - k), n - 1) { int mex = rs.mex(0); grundy[ni] = mex; cnt[grundy[ni]]++; rs.insert(grundy[ni], grundy[ni] + 1); } REPD(ni, max(0LL, n - 1 - k)) { // 尺取り cnt[grundy[ni + k + 1]]--; if (cnt[grundy[ni + k + 1]] == 0) rs.erase(grundy[ni + k + 1], grundy[ni + k + 1] + 1); cnt[grundy[ni + 1]]++; rs.insert(grundy[ni + 1], grundy[ni + 1] + 1); int mex = rs.mex(0); grundy[ni] = mex; } return grundy[0]; } void solve(int n, int k) { if (get_grundy(n, k) == 0) { print("Lose"); } else { print("Win"); } } signed main() { cin >> p; VI N(p), K(p); REP(pi, p) { cin >> N[pi] >> K[pi]; } REP(pi, p) { solve(N[pi], K[pi]); } return 0; }