Một quân cờ ở ô n trên dải 0,…,n. Alice đi trước; mỗi lượt phải dịch quân sang trái 1,2 hoặc k ô mà không ra ngoài. Người không đi được thua.
Input
Dòng đầu chứa t; mỗi test gồm hai số nguyên n,k.
Output
Với mỗi test, in Alice hoặc Bob.
Constraints
1≤t≤100.
0≤n≤1018,3≤k≤1018.
Scoring
Subtask 1 (50% số điểm): các test 1-10 có kích thước nhỏ, thuận tiện kiểm chứng độc lập.
Subtask 2 (50% số điểm): không có giới hạn bổ sung ngoài các cận đã nêu.
Example
Test 1
Input
1
0 3
Output
Bob
Giải thích: Với n=0, không thể trừ 1, trừ 2 hay chia cho k. Người đi trước không có nước hợp lệ, nên in Bob.
Lời giải tóm tắt
Ý tưởng và thuật toán: Nếu k%3!=0, các trạng thái thua chính là n%3==0.
Ý tưởng và thuật toán: Nếu k%3==0, đặt r=n%(k+1). Trạng thái thua khi r là bội của 3 nhưng r!=k.
Ý tưởng và thuật toán: Từ đó in Alice nếu không thuộc tập thua.
Chứng minh đúng đắn: Khi k%3!=0, từ bội của 3, trừ 1, 2 hoặc k đều đi tới lớp không chia hết cho 3; từ lớp 1/2, luôn trừ 1/2 để về bội 3. Đây là phân loại P/N hoàn chỉnh.
Chứng minh đúng đắn: Khi k%3=0, xét từng khối độ dài k+1. Tập thua trong một khối là các residue 0,3,6,...,k-3.
Chứng minh đúng đắn: Từ một residue thua, trừ 1 hoặc 2 cho residue không chia hết cho 3; trừ k tương đương tăng residue lên 1 ở khối trước, cũng không thuộc tập thua.
Chứng minh đúng đắn: Từ residue 1 mod 3, trừ 1 về thua; từ 2 mod 3, trừ 2; riêng residue k có thể trừ k về residue 0.
Chứng minh đúng đắn: Vì mọi trạng thái ngoài tập có nước vào tập và mọi nước từ tập đi ra ngoài, công thức đúng.