Cho số nguyên dương ~n~ và dãy số nguyên dương ~a_1, a_2, \dots, a_n~. Với mỗi cặp chỉ số ~(i, j)~ thỏa mãn ~1 \le i \le j \le n~, ta thực hiện phép biến đổi sau:

• Thay đoạn con liên tiếp ~a_i, a_{i+1}, \dots, a_j~ bằng một số duy nhất có giá trị ~\operatorname{lcm}(a_i, a_{i+1}, \dots, a_j)~, trong đó ~\operatorname{lcm}~ là bội chung nhỏ nhất.

• Khi đó, dãy thu được gồm các phần tử ~a_1, \dots, a_{i-1}, \operatorname{lcm}(a_i, \dots, a_j), a_{j+1}, \dots, a_n~.

Giá trị của dãy sau phép biến đổi được định nghĩa là:

~f(i, j) = \gcd(a_1, \dots, a_{i-1}, \operatorname{lcm}(a_i, \dots, a_j), a_{j+1}, \dots, a_n)~,

trong đó ~\gcd~ là ước chung lớn nhất.

Yêu cầu: Tính tổng ~S = \sum_{i=1}^{n}\sum_{j=i}^{n} f(i, j)~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 2 \cdot 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^7)~.

Output

Một số nguyên duy nhất là giá trị ~S~, lấy theo modulo ~998244353~.

Scoring

Sample Input 1

5
2 6 9 3 6

Sample Output 1

44

Sample Input 2

6
1 2 3 4 5 6

Sample Output 2

85