시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 59 24 20 52.632%

문제

Alice와 Bob은 N개의 정사각형을 일렬로 놓고 게임을 하고 있다. 정사각형에는 1부터 N까지의 수가 하나씩 적혀져 있다.

Alice와 Bob은 턴을 번갈아가면서 수를 하나씩 제거한다. 어떤 정사각형에 적혀있는 수를 제거하려면, 변을 공유하는 양쪽 정사각형에 더 큰 수가 있으면 안된다. 수를 제거하면, 정사각형에는 수가 적혀있지 않은 상태가 된다.

1을 제거하는 사람이 게임을 승리한다. 게임의 초기 상태가 주어졌을 때, 두 사람이 최적의 방법으로 게임을 한다면, 누가 이기는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100) 가 주어진다. 각 테스트 케이스의 첫째 줄에는 N (1 ≤ N ≤ 100)이 주어진다. 다음 줄에는 게임의 초기 상태가 왼쪽부터 오른쪽까지 순서대로 주어진다.

출력

각각의 테스트 케이스에 대해서, 게임을 승리하는 사람을 출력한다.

예제 입력 1

4
4
2 1 3 4
4
1 3 2 4
3
1 3 2
6
2 5 1 6 4 3

예제 출력 1

Bob
Alice
Bob
Alice
W3sicHJvYmxlbV9pZCI6IjEwNTYzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODE1XHVjMjE4IFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL251bWJlcmdhbWUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OTRweDsgd2lkdGg6MzMzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QWxpY2VcdWM2NDAgQm9iXHVjNzQwIE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWIxOTNcdWFjZTAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMFx1YjI5NCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzBcdWM3NTggXHVjMjE4XHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5BbGljZVx1YzY0MCBCb2JcdWM3NDAgXHVkMTM0XHVjNzQ0IFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWMyMThcdWI5N2MgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzgxY1x1YWM3MFx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViNWE0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjMjE4XHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YjgyNFx1YmE3NCwgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU1OFx1YjI5NCBcdWM1OTFcdWNhYmQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwIFx1YjM1NCBcdWQwNzAgXHVjMjE4XHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1YzIxOFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NThcdWJhNzQsIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMFx1YjI5NCBcdWMyMThcdWFjMDAgXHVjODAxXHVkNjAwXHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMwYzFcdWQwZGNcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD4xXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJiOVx1YjlhY1x1ZDU1Y1x1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWNkNWNcdWM4MDFcdWM3NTggXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YjIwNFx1YWMwMCBcdWM3NzRcdWFlMzBcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKDEgJmxlOyBUICZsZTsgMTAwKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE4gKDEgJmxlOyBOICZsZTsgMTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YWU0Y1x1YzljMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJiOVx1YjlhY1x1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNTYzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTnVtYmVyIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL251bWJlcmdhbWUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OTRweDsgd2lkdGg6MzMzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QWxpY2UgYW5kIEJvYiBhcmUgcGxheWluZyBhIGdhbWUgb24gYSBsaW5lIG9mIE4gc3F1YXJlcy4gVGhlIGxpbmUgaXMgaW5pdGlhbGx5IHBvcHVsYXRlZCB3aXRoIG9uZSBvZiBlYWNoIG9mIHRoZSBudW1iZXJzIGZyb20gMSB0byBOLiBBbGljZSBhbmQgQm9iIHRha2UgdHVybnMgcmVtb3ZpbmcgYSBzaW5nbGUgbnVtYmVyIGZyb20gdGhlIGxpbmUsIHN1YmplY3QgdG8gdGhlIHJlc3RyaWN0aW9uIHRoYXQgYSBudW1iZXIgbWF5IG9ubHkgYmUgcmVtb3ZlZCBpZiBpdCBpcyBub3QgYm9yZGVyZWQgYnkgYSBoaWdoZXIgbnVtYmVyIG9uIGVpdGhlciBzaWRlLiBXaGVuIHRoZSBudW1iZXIgaXMgcmVtb3ZlZCwgdGhlIHNxdWFyZSB0aGF0IGNvbnRhaW5lZCBpdCBpcyBub3cgZW1wdHkuIFRoZSB3aW5uZXIgaXMgdGhlIHBsYXllciB3aG8gcmVtb3ZlcyB0aGUgMSBmcm9tIHRoZSBsaW5lLiBHaXZlbiBhbiBpbml0aWFsIGNvbmZpZ3VyYXRpb24sIHdobyB3aWxsIHdpbiwgYXNzdW1pbmcgQWxpY2UgZ29lcyBmaXJzdCBhbmQgYm90aCBvZiB0aGVtIHBsYXkgb3B0aW1hbGx5PzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgYmVnaW5zIHdpdGggYSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciBULCAxICZsZTsgVCAmbGU7IDEwMCwgZGVub3RpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBiZWdpbnMgd2l0aCBhIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIE4sIDEgJmxlOyBOICZsZTsgMTAwLCBkZW5vdGluZyB0aGUgc2l6ZSBvZiB0aGUgbGluZS4gTmV4dCBpcyBhIGxpbmUgd2l0aCB0aGUgbnVtYmVycyBmcm9tIDEgdG8gTiwgc3BhY2Ugc2VwYXJhdGVkLCBnaXZpbmcgdGhlIG51bWJlcnMgaW4gbGluZSBvcmRlciBmcm9tIGxlZnQgdG8gcmlnaHQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCB0aGUgbmFtZSBvZiB0aGUgd2lubmluZyBwbGF5ZXIgb24gYSBzaW5nbGUgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=