GCD Quadruple Sum

Given an integer N, compute the sum

$$S = \sum_{i=1}^N \sum_{j=1}^N \sum_{p=1}^{\lfloor \frac{N}{j} \rfloor} \sum_{q=1}^{\lfloor \frac{N}{j} \rfloor} [\gcd(i,j)=1] [\gcd(p,q)=1] \pmod{998244353},$$

where the notation \([P]\) evaluates to 1 if the proposition P is true, and 0 otherwise.

You are required to compute S modulo 998244353.

inputFormat

The input contains a single integer N (N ≥ 1).

You may assume that N is small enough to allow a brute force solution.

outputFormat

Output the computed sum S modulo 998244353.

sample

1

1