蒂蒂和鲨鲨的头脑博弈游戏

题目描述

蒂蒂和鲨鲨正在玩一种游戏，规则如下： 初始时有一堆数量为n的石子，每次操作可取走1或2或3个石子，取完结束，蒂蒂先手，设蒂蒂每一步依次取走$a_1$，$a_2$，$a_3$...$a_k$个石子，若$a_1$⊕$a_2$⊕$a_3$...⊕$a_k$=0，则蒂蒂获胜，反之鲨鲨获胜。 她们一共进行了T轮游戏，请聪明的你判断每一轮游戏谁是获胜者。

输入格式

第一行一个整数$T(1 \le T \le 10^5)$，表示游戏论数。 随后T行，每行一个正整数$n(1 \le n \le 10^9)$，表示初始石子数。

输出格式

对于每轮游戏，输出一行，若蒂蒂获胜输出“didi”(不含引号)，反之输出“shasha”（不含引号）

样例 #1

样例输入 #1

3
1
2
3

样例输出 #1

shasha
shasha
shasha

提示

对于这三轮游戏，无论蒂蒂如何取石子，都无法获胜