Tổng hàm Euler

Trong một dự án xây dựng mới, FullHouse Dev đang phải đối mặt với một bài toán thú vị về lý thuyết số. Họ cần tính toán tổng của một chuỗi các giá trị đặc biệt dựa trên hàm phi Euler.

Bài toán

Cho một số nguyên dương \(N\). Hàm phi Euler \(\phi(n)\) đếm số lượng số nguyên dương nhỏ hơn hoặc bằng \(n\) mà nguyên tố cùng nhau với \(n\). Định nghĩa hàm \(F(N)\) là tổng của \(\phi(i)\) với \(i\) chạy từ \(1\) đến \(N\). Nhiệm vụ của FullHouse Dev là tính giá trị của \(F(N)\) theo modulo \(10^9 + 7\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Mỗi test case gồm một dòng chứa một số nguyên dương \(N\).

OUTPUT FORMAT:

• Với mỗi test case, in ra một dòng duy nhất chứa giá trị của \(F(N)\) sau khi chia lấy dư cho \(10^9 + 7\).

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq N \leq 10^6\)

Ví dụ

INPUT

2
2
3

OUTPUT

3
11

Giải thích

• Test case 1: \(N = 2\)
  • \(F(2) = \phi(1) + \phi(2) = 1 + 1 = 3\)
• Test case 2: \(N = 3\)
  • \(F(3) = \phi(1) + \phi(2) + \phi(3) = 1 + 1 + 2 = 4\)