This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2286"
#include <iostream>
#include "C++/math/phitable.hpp"
constexpr int n = 1e6;
int main() {
const auto phi = man::phi_table(n).get();
std::vector<int64_t> ret(n + 1);
ret[1] = 2;
for(int i = 2; i <= n; ++i) {
ret[i] = ret[i - 1] + phi[i];
}
int t;
std::cin >> t;
while(t--) {
int i;
std::cin >> i;
std::cout << ret[i] << '\n';
}
}
#line 1 "test/phi_table.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2286"
#include <iostream>
#line 2 "C++/math/phitable.hpp"
#include <vector>
#include <numeric>
#include <ranges>
namespace man {
struct phi_table {
private:
int n;
std::vector<int> euler;
public:
phi_table(const int n_): n(n_), euler(n_ + 1) {
std::iota(euler.begin(), euler.end(), 0);
for(const auto i: std::views::iota(2, n + 1)) {
if(euler[i] == i) {
for(int j = i; j <= n; j += i) {
euler[j] = euler[j] / i * (i - 1);
}
}
}
}
inline std::vector<int> get() const noexcept { return euler; }
};
}
/**
* @brief Euler's Phi-function(table)
*/
#line 4 "test/phi_table.test.cpp"
constexpr int n = 1e6;
int main() {
const auto phi = man::phi_table(n).get();
std::vector<int64_t> ret(n + 1);
ret[1] = 2;
for(int i = 2; i <= n; ++i) {
ret[i] = ret[i - 1] + phi[i];
}
int t;
std::cin >> t;
while(t--) {
int i;
std::cin >> i;
std::cout << ret[i] << '\n';
}
}