1983: 又一个数字游戏
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：6
题目描述
小明拿出了一个素数集合，{2, 3, 5, 7, 11, 13, …, 127, …}，他发现，从小到大排序后，127是第31个数，而31也在素数集内，31是第11个数，11是第5个数，5是第3个数，3是第2个数，2是第1个数。
而127，31，11，5，3，2都为素数。
这时，小明又发明了一个游戏，给出一个n，取出一个{2, 3, 4, …, n}的一个子集，子集中必须包含n。将取出子集中的数从小到大排序后，他先取出n，n是第k1大的数，再取出k1，k1是第k2大的数，再取出k2……这样不断下去，最后能取出最小的数。对于给定的n，为{2, 3, 4, …, n}的子集中有多少个满足要求。
输入
第一行包含一个正整数T，表示了数据组数。
接下来T行，每行一个不小于2的正整数n，如题目所述。
输出
包括T行，对于每个n输出相应答案，由于答案可能很大，你需要输出答案mod 100003后的结果，请注意可能要使用int64或者long long。
样例输入 复制
2
5
6
样例输出 复制
5
8
提示
【样例说明】
对于n=5，有以下5个答案：
{5}, {2, 5}, {2, 3, 5}, {2, 3, 4, 5}, {3, 4, 5}
{2, 4, 5}不行是因为5是第3大的数，3不在集合中。
{3, 5}同样也不行，因为5是第2大的数，2不在集合中。
对于n = 6
{3, 4, 5, 6}不行是因为6是第4大的数，4是第2大的数，2不在集合中。
【数据规模与约定】
对于20%的数据，有T≤5, N≤12；
对于60%的数据，有T≤50，N≤100；
对于100%的数据，有T≤500，N≤500。