Đã một năm trôi qua kể từ đại dịch \(COVID-X\) xuất hiện. Rất may kỳ thi năm đó ban tổ chức đã giải quyết được vấn đề chia phòng nhờ bạn. Nhưng năm nay đại dịch \(COVID-X\) đã có biến thể mới là \(COVID-LCM\) còn mạnh hơn trước.

Ở khu bạn sống, có \(n\) người sống cùng nhau. Biết người thứ \(𝑖\) đã tiêm tổng cộng là \(a_i\) liều vaccine theo chỉ đạo của chính phủ. Biết rằng khi hai người \(𝑖\) và \(𝑗\) tiếp xúc thì độ an toàn của cặp đó là \(LCM(a_i ,a_j)\) vì càng tiêm nhiều vaccine thì càng an toàn. Và độ an toàn của một khu được tính bằng tổng của tất cả độ an toàn của tất cả các cặp người sống ở đó.

Yêu cầu: Tính độ an toàn của của khu vực bạn sống. Kết quả chia lấy dư cho \(998244353\).

Input

• Dòng 1 chứa số nguyên \(n\) (\(1 ≤ n ≤ 2*10^5)\).

• Dòng 2 chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1 ≤ a_i ≤ 10^6)\).

Output

• Ghi một số là độ an toàn của của khu vực bạn sống. Kết quả chia lấy dư cho \(998244353\).

Giới hạn:

• Subtask 1: \(1 ≤ n ≤ 1000\)

• Subtask 2: \(1 ≤ n ≤ 8000,1 ≤ a_i ≤ 1000\)

• Subtask 3: Không có thêm ràng buộc nào cả.

Sample Input

8
15 9 4 7 14 1 15 14

Sample Outout

1830