春假已经结束了。尽管你觉得一周的假期（像往常一样）远远不够，但你知道是时候恢复工作了。突然，你意识到下周有一场数论期中考试。当你浏览教授给出的所有练习题时（你本应该在假期里完成的），你发现有一种题目你完全不知道怎么做。题目形式如下：给定一个数 $n$，计算 $n$ 的所有约数之和，但不包括 $n$ 本身。更糟糕的是，由于你这学期从没去上过课（这并不令人惊讶），你根本不知道从哪里开始。不过，幸运的是，教授承诺考试中给出的 $n$ 将属于某个特定的数字集合。因此，只要你能记住所有可能的结果，就没问题了。由于给定集合的大小相当大，你希望编写一个程序在开始背诵之前计算出所有答案。

输入格式

第一行包含一个整数 $q \le 10^6$，表示考试中给出的 $n$ 的可能数量。第二行包含 $a_1$，即第一个被问到的问题，满足 $1 \le a_1 \le 10^6$。其余问题将通过以下规则生成：

$$a_{i+1} = (a_i^2 \pmod{999983}) + 1 \quad \forall i \in \{1 \dots q - 1\}$$

输出格式

输出一行，包含一个整数，即对于所有 $1 \le i \le q$，以 $n = a_i$ 为问题的答案之和。

样例

样例输入 1

3
2

样例输出 1

18

说明

在样例测试用例中，问题 $n = 2$ 的答案为 $1$；问题 $n = 5$ 的答案为 $1$；问题 $n = 26$ 的答案为 $16$。输出的答案应为 $1 + 1 + 16 = 18$。