桃子和杏子玩取石子游戏,有n堆石子,第i堆有a_i个,她们轮流取石子,桃子先取,她们每次都只能选一堆未取完的石子。然后,桃子可以从这堆石子中取走1或2个石子,而杏子每次只能取走1个石子。谁把最后的石子取完,使得另外一个人没法操作,谁就获得了胜利。两人都在最优策略下取石子,请问最终谁获胜?
输入
第一行输入一个数T(1\le T\le20000),然后会有2T行:一行一个数n(1\le n\le100),代表石子堆数,另一行n个数a_1,a_2,\cdots,a_n,表示每一堆石子的数量(1\le a_i\le100)。
输出
对于每组测试,输出一行,若桃子胜,输出momoko
,若杏子胜,输出sakiko
。
样例
标准输入 复制文本 |
2 2 1 3 2 1 1 |
标准输出 复制文本 |
momoko sakiko |
提示
对于第一组,桃子可以先取完第一堆,然后杏子只能从第二堆取走一个,第三步桃子取完石子,桃子胜。
计院 2020CS 杯真题D题