题目描述

设有两个二维向量 $\vec{A}(X_A, Y_A), \vec{B}(X_B, Y_B)$。

给定一个正整数 $L$，请你计算满足下列条件的四元组 $(X_A, Y_A, X_B, Y_B)$ 的数量：

• $X_A, Y_A, X_B, Y_B$ 均为正整数；
• $\vec{A} \cdot \vec{B} \le L$。

其中，$\vec{A} \cdot \vec{B}$ 表示向量的内积，即 $X_A \cdot X_B + Y_A \cdot Y_B$。

请输出满足条件的不同取值方案数。

说明：四元组不同当且仅当 $(X_A, Y_A, X_B, Y_B)$ 中至少有一个对应位置的值不同。

输入格式

输入一行，包含一个正整数 $L$。

输出格式

输出一行，包含一个整数，表示满足条件的方案数。

样例输入 1

2

样例输出 1

1

样例输入 2

3

样例输出 2

5

样例输入 3

114514

样例输出 3

835075530409

说明

样例解释

对于样例 $2$，分别有 $5$ 种方案：$(1, 1, 1, 1)$、$(1, 1, 2, 1)$、$(1, 2, 1, 1)$、$(2, 1, 1, 1)$、$(1, 1, 1, 2)$。

数据范围

对于 $100\%$ 的数据，$1 \le L \le 2^{20}$。

各测试点的附加限制如下表所示：

点击下载大样例