HZNUOJ

千年等一回

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:271     AC:120     Score:92.51

Description

“千年等一回 等一回啊“

“千年等一回 我无悔啊”

“是谁在耳边 说 爱我永不变”

“只为这一句 啊哈断肠也无怨”

白蛇传是中国古代民间爱情传说故事之一。发生在宋朝时的杭州、苏州及镇江等地。白素贞是千年修炼的蛇妖,为了报答书生许仙前世的救命之恩,化为人形欲报恩,后遇到青蛇精小青,两人结伴。白素贞施展法力,巧施妙计与许仙相识,并嫁与他。婚后金山寺和尚法海对许仙讲白素贞乃蛇妖,许仙将信将疑。后来许仙按法海的办法在端午节让白素贞喝下带有雄黄的酒,白素贞不得不显出原形,却将许仙吓死。白素贞上天庭盗取仙草将许仙救活。

白娘子盗仙草的时候,被看守仙草的童子发现了,童子正在想一道数学题,想不出来,抓到了白娘子,所以嘿嘿一笑,要白娘子来想这道题,否则就要把白娘子盗仙草的事情禀报给天庭。

这道题是这样的,告诉你一个$n$,$m=1^{10000}+2^{10000}+……n^{10000}$,问m除以3的余数是多少?

白娘子法力无边,所以召唤了一个锦囊。

锦囊里写着:

设$p$除以$c$的余数是$a$,$q$除以$c$的余数是$b$。

若$m=(p+q)$

则$m\%c  =  (a+b)\%c$;

若$m=p\cdot q$

则$m\% c=(a\cdot b)\% c$

$(p\cdot p\cdot p)\% c = (p\%c)\cdot (p\%c)\cdot (p\%c)$ 

 

为了救活许仙,请你帮白娘子做一下这道题。

Input


第一行一个$t$,然后是t组输入,$t\leq 5$

每组输入都是一个正整数$n$,$n\leq 100000$.


Output

对于每组输入,输出一行,即算式的余数。

Samples

input
3 1 2 3
output
1 2 2
input
1 100000
output
1

Hint

锦囊里的知识或许可以帮你解决这道题

Author

YU, Saikang