Alice пен Bob орын ауыстыруда (пермутацияда) ойын ойнап жатыр, ойынды Alice бірінші болып бастайды.
Ұзындығы $n$ болатын тізбек орын ауыстыру деп аталады, егер және тек егер $1, 2, \ldots, n$ аралығындағы әрбір бүтін сан тізбекте дәл бір рет кездессе.
Бастапқыда ұзындығы $n$ болатын $a_1, a_2, \ldots, a_n$ орын ауыстыруы берілген. Ойын барысындағы кез келген сәтте ағымдағы тізбек әрқашан қандай да бір $m$ ұзындықтағы орын ауыстыру болып табылады. Ойыншылар кезекпен жүреді, және әр жүрісте ағымдағы ойыншы келесі екі амалдың бірін таңдауы тиіс:
- $a_i > a_{i+1}$ шартын қанағаттандыратын $i$ ($1 \le i < m$) индексін таңдап, $a_i$ мен $a_{i+1}$ элементтерінің орындарын ауыстыру;
- $a_{i+1} = a_i + 1$ шартын қанағаттандыратын $i$ ($1 \le i < m$) индексін таңдап, $a_i$ мен $a_{i+1}$ элементтерін өшіріп, содан кейін қалған элементтерді олардың салыстырмалы ретіне сәйкес қайта нөмірлеу: қалған элементтердің ішіндегі өсу ретімен $k$-ші ең кіші элемент $k$ болып қайта нөмірленеді, нәтижесінде қалған тізбек қайтадан орын ауыстыруға айналады.
Мысалы, ағымдағы орын ауыстыру $[2, 3, 4, 1]$ болсын делік. Көршілес $2$ және $3$ элементтерін өшіруге болады, сонда $[4, 1]$ қалады; қайта нөмірлегеннен кейін орын ауыстыру $[2, 1]$ болады.
Ешқандай амал орындай алмайтын ойыншы ойында жеңіледі. Alice те, Bob та тиімді (оптималды) ойнайды деп есептеп, жеңімпазды анықтаңыз.
Кіріс деректер
Әрбір тест бірнеше тест жағдайларынан тұрады.
Бірінші жолда бір бүтін сан $T$ ($1 \le T \le 5000$) — тест жағдайларының саны берілген.
Әрбір тест жағдайы үшін:
- Бірінші жолда бір бүтін сан $n$ ($1 \le n \le 5000$) берілген.
- Екінші жолда $n$ бүтін сан $a_1, a_2, \ldots, a_n$ берілген. $a$ ұзындығы $n$ болатын орын ауыстыру екеніне кепілдік беріледі.
Барлық тест жағдайлары бойынша $n$ мәндерінің қосындысы $5000$-нан аспайтынына кепілдік беріледі.
Шығыс деректер
Әрбір тест жағдайы үшін, егер Alice жеңсе, Alice деп, әйтпесе Bob деп шығарыңыз.
Мысалдар
Кіріс деректер 1
5 1 1 2 1 2 2 2 1 4 2 4 1 3 5 5 1 4 2 3
Шығыс деректер 1
Bob Alice Bob Alice Bob