描述

King.Songer 在外出打仗时，也没有放松自己本土的防御。 在冷兵器时代，将士们都喜欢让自己的士兵把自己围起来，自己则在阵式中心发号施令。

King.Songer 是一个很擅长数学的将领，他发现，如果把士兵们围成一个三角形，不仅进攻灵活，防守也固若金汤。更进一步的，假定他使用了 \(a,b,c\) 个士兵围成了三条边，根据神秘的东方力量，这个阵应该满足 \(a^2+b^2=c^2+1\) 来达到最大的攻击和防御力。

现在 King.Songer 共计有 \(n\) 位士兵，他想知道，在总使用士兵数不超过 \(n\) 的情况下，共计有多少种不同的布阵方法？因为阵式是可以旋转的，所以他只想知道 \(a \le b \le c\) 的布阵方法。

输入

输入仅包含一个整数 \(n(3 \le n \le 2 \times 10^6)\)，代表 King.Songer 拥有的兵力总数。

输出

在一行中输出两个整数：第一个整数为满足要求的三元组的个数，第二个整数为 \(⨁(a + b) ⊕ c\)，即两条短边和异或上长边和的异或和。

输入样例 #1

10

输出样例 #1

4 4

输入样例 #2

2000000

输出样例 #2

4219646 489062

样例解释

对于第一个输入样例，共有四组满足条件的三元组：\((1, 1, 1),(1, 2, 2),(1, 3, 3),(1, 4, 4)\)。