OI题库

题目描述：

         在小学一、二年级的时候，Admin有一个理想，那就是去写一本万年历。聪明的他发现，如果知道每年的1月1日是星期几，便很容易写出整年的日历。于是他开始找到一个账本写下了每一年1月1日是星期几（还常常被父母叫为“黄世仁帐”），具体写了多少本，写到多少年，现在已经印象不清了，不过写到几万年是肯定有的。

         天真的Admin就这样在账本上写啊写啊，直到有一天，出现了一个人，告诉了Admin可以用Excel来写（使用的还是Excel97），不过由于某种技术原因，并没有实现计算机自动计算（当时Admin还没有真正的用过电脑呢），也仅仅是将账本上手写变成了在计算机键盘上输入。

         这个项目一直到大约到Admin小学三年级的时候才结束，当时小学数学课本正在讲日历。在课本的底部的注释上写着的一句话，让他发现，原来自己判断闰年的方式有误，没有考虑整百年的情况。于是这个项目也就停止了……

         这个理想一直在Admin心中，在初中学习了程序设计后，他也首次成功的用计算机完成了这个任务。不过，让Admin感触最深的是当他做USACO，查看某一个题解时发现的“蔡勒公式”让他知道，原来数学是多么的伟大。

         现在呢，就请你穿越到Admin小时候，帮助他来完成这个任务吧。（咦？现在的Admin不用帮了吗？哦。。。原来他已经会做了……）

         （不需要考虑真实历史在某年跨越了几天的问题，闰年的判断方式为整百年被400整除，非整百年被4整除）

 输入格式：

第一行一个整数case，表示测试组数

下面有case行，每行有一个整数n，表示一个年份

 输出格式：

对于每一个case输出一行，表示当前年份的1月1日是星期几，用一个0到6的数字来表示（1表示星期一，2表示星期二，3表示星期三，4表示星期四，5表示星期五,6表示星期六，0表示星期日）

 输入样例：

2

1

2012

 输出样例

1

0

 输入规模：

10%的数据 case=1  n=2008

30%的数据 n<=10^5

50%的数据 n<=10^9

100%的数据 1<=n<=10^10000  case<=10