Totient Sums

**Problem.** Line 1: q. Each line: N. Print sum_{k=1..N} phi(k) mod 1e9+7. **Constraints:** 1 ≤ q ≤ 2000; 1 ≤ N ≤ 10^6. Linear phi sieve + prefix sums once, then O(1) per query.