Tổng các số chính phương chia cho 3 dư 1


Submit solution

Points: 2 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Số chính phương là một số tự nhiên sao cho tồn tại một số tự nhiên bình phương bằng nó ví dụ \(0, 1, 4, 9, 16, ...\)

Bài toán đặt ra: Cho số tự nhiên \(n\) hãy tính tổng tất cả các số chính phương chia cho 3 dư 1 và nhỏ hơn hoặc bằng \(n\)

Input

Dòng đầu là số bộ test \(t (1 \le t \le 100)\)

\(t\) dòng tiếp theo mỗi dòng chứa một số tự nhiên \(n\) không vượt quá \(10^9\)

Output

Gồm t dòng mỗi dòng là kết quả bài toán vì số quá lớn nên ta chỉ lấy phần dư của kết quả chia cho 1000000007 \((10^9+7)\)

Ví dụ

Input

3
10
36
37

Output

5
46
46

Giải thích

Với \(n=10\) ta có các số chính phương nhỏ hơn \(10\) chia cho 3 dư 1 là \(0 ,1 ,4 \) có tổng \(5\)

Với \(n=36\) hoặc \(n=37\) ta có các số chính phương nhỏ hơn \(n\) chia cho 3 dư 1 là \(0 ,1 ,4, 16, 25 \) có tổng \(46\)

Chú ý Đây là bài dễ bài khó hơn tại Lại là tổng các số chính phương chia cho 3 dư 1

tichpx

Comments


  • 4
    DuyAnhhh  commented on Sept. 21, 2020, 3:41 p.m.

    Bài này hình như test có số to hơn 10^9 thầy ạ