# f(n) : 2n^2の約数のうち,n以下のものの個数
# F(n) : sum_(n=1..n)f(n)
# f(15) = 8
# F(15) = 63
# F(1000) = 15066
# F(10^12)を求めよ

from collections import defaultdict
def guchok_f(n):
    m = 2*n**2
    i = 2
    count = 1
    while i<=n:
        if m%i==0:
            count += 1
        i += 1
    return count

def guchok_F(n):
    count = 0
    for i in range(1, n+1):
        count += guchok_f(i)
    return count

print(guchok_f(15))
print(guchok_F(15))
print(guchok_F(1000))

# 以上の計算量はf(n)でO(n)だから合計でO(n^2)
# print(guchok_F(10**5))
# 上が大体52秒くらいかかる

# k が2n^2の約数となるk<=n<=Nの個数g(k)を考える
# sum(k=1..N)g(k) = F(N)となる
# k を素因数分解してa1^b1*a2^b2...ai^biとなるとする。

# k' = a1^(-(-b1//2)-1)a2^(-(-b2//2))...として、N以下k以上のk'の倍数の個数を数えればいい。
# a1=2, a2=3...となってるとしている。a1だけ先に-1して、a1..iを全て2で割って繰り上げ

import itertools
import collections
from math import gcd
def prime_factor_table(n):
    table = [0] * (n + 1)
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    return table

def prime_factor(n, prime_factor_table):
    prime_count = dict()
    while prime_factor_table[n] != 0:
        if prime_factor_table[n] not in prime_count:
            prime_count[prime_factor_table[n]] = 0
        prime_count[prime_factor_table[n]] += 1
        n //= prime_factor_table[n]
    if n not in prime_count:
        prime_count[n] = 0
    prime_count[n] += 1
    return prime_count

def yakusu_base_F(n):
    pp = prime_factor_table(n)
    R = 0
    R2 = 0
    for i in range(1, n+1):
        tt = prime_factor(i, pp)
        x = 1
        for key in tt:
            v = tt[key]
            if key == 2:
                v-=1
            x *= key**-((-v)//2)
        diff = (n-i)//x + 1
        diff2 = n//x - i//x+1
        R += diff
        R2 += diff2
#        if diff>-1:
#            print(n, i,x, diff)
#            print(n, i,x, diff2)
#            print(tt)
    return R, R2

# 以上の計算だと以下が0.49sかかる。O(NlogN)
# print(yakusu_base_F(10**6))
# k'ごとにカウントすればさらに高速化できる。
# k'=p1^q1 * p2^q2...pt^qt
# になるようなk'が奇数ならkは2^(t+1)個、偶数なら2^(t)個ある

print(yakusu_base_F(10**8))

def yakusu_base_F_test(n):
    pp = prime_factor_table(n)
    R = 0
    d = defaultdict(set)
    count = 0
    for i in range(1, n+1):
        tt = prime_factor(i, pp)
        x = 1
        for key in tt:
            v = tt[key]
            if key == 2:
                v-=1
            x *= key**-((-v)//2)
        diff = (n-i)//x+1
        d[x].add((i, diff))
        if diff <= 1000:
#            print(i, x, diff)
            count += 1
#        if diff>30:
#            print(i, diff)
        R += diff
    print(len(d))
#    keys = sorted(list(d.keys()))
#    for key in keys:
#        print(key, d[key])
#    print(count)
    return R
#print(yakusu_base_F_test(10**3))