D. Too much noise!
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

While solving the puzzle Look For a Needle in a Bottle of Hay, Locytus is looking for the information among the signals, but there is too much noise!

Locytus wants to classify the signals. Each signal $$$S_i$$$ has two attributes represented by integers, energy $$$a_i$$$ and frequency $$$b_i$$$. For two signals $$$S_i=(a_i,b_i),S_j=(a_j,b_j)$$$, the difference between them is $$$d(S_i, S_j):=\lvert a_i-a_j\rvert\times \frac{b_ib_j}{\gcd(b_i,b_j)^2}$$$, where $$$\gcd(b_i,b_j)$$$ is the greatest common divisor of $$$b_i$$$ and $$$b_j$$$.

The first step in classification is to calculate the sum of differences among all different signals, which is $$$\sum_{i=1}^n\sum_{j=1}^n d(S_i,S_j)$$$. But Locytus is exhausted after collecting the signals, please tell him the result of the sum.

The answer may be very large, please output it after modulo $$$998244353$$$.

Input

The first line contains a single integer $$$n$$$ $$$(2\le n \le 2\times 10^5)$$$, representing the number of signals.

The second line contains $$$n$$$ integers separated with spaces, the $$$i$$$-th integer represents the $$$i$$$-th signal's energy $$$a_i$$$ $$$(1\le a_i \le 2\times 10^5)$$$.

The third line contains $$$n$$$ integers separated with spaces, the $$$i$$$-th integer represents the $$$i$$$-th signal's frequency $$$b_i$$$ $$$(1\le b_i \le 2\times 10^5)$$$.

Output

Output a single integer, representing the sum of differences among all different signals after modulo $$$998244353$$$.

Examples
Input
2
1 2
2 3
Output
12
Input
4
1 15 17 11
2 15 3 16
Output
3708