Problem:


Score : 700 points

Problem Statement

We have an integer sequence of length N: A_0,A_1,\cdots,A_{N-1}.

Find the following sum (\mathrm{lcm}(a, b) denotes the least common multiple of a and b):

\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j)

Since the answer may be enormous, compute it modulo 998244353.

Constraints

1 \leq N \leq 200000

1 \leq A_i \leq 1000000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0\ A_1\ \cdots\ A_{N-1}

Output

Print the sum modulo 998244353.

Sample Input 1

3
2 4 6

Sample Output 1

22

\mathrm{lcm}(2,4)+\mathrm{lcm}(2,6)+\mathrm{lcm}(4,6)=4+6+12=22.

Sample Input 2

8
1 2 3 4 6 8 12 12

Sample Output 2

313

Sample Input 3

10
356822 296174 484500 710640 518322 888250 259161 609120 592348 713644

Sample Output 3

353891724



Sample input:
3
2 4 6


Sample output:
22

Submission status: Wrong Answer

Solution code:
import subprocess
import gzip, base64, os
import stat

gz = b'H4sIAJRXh10C/+19e3xTRfb4TfogvJqCiBVBCwZpRUpDC7Q+lpYSuIEUurQgKngJaUqjadNNbkpZX7ht1RiqfNV1+X73xW8f/txdd9fvrusiKrS8ii8EH4iigK5IQkWLKBSR5nfOzNx07k1uhd39fj+/P7xKJ+fcMzPnnDlz5szcuXPvsTlmGw0GQbmMwvcEhJyjSwhcwvDrA3ESwBUJA+HvFcJoIR3gNI6uRChRpT2saCU1MboU+JcK/4qMFC4ylqjS0YxOSQ1cmibwV4kqvX6FoEoFITueD3ndX0ex++uWq9LsVIrPH6DOZ2T5eli+HkavpIJRUKWKfKnsXxXDVzG5lHQWo5vF0eNVcUSuxt8bb6HwxltKVOlaRrdWk+/7kC9dOP8rk6ULWX16eslh/Cup0g6TvZ4V0wone6sneT31waZJTUXTJk0rzAv48qYQnjIZ7Zz5i1R6zGI8j2A2gPcPPP7Oa+Ldr955cdeu4Wd9tXd+M9qShfeuY/mwSVrrM2tTxw40GoRCYQ0Ujfe+B//K4N9f3i94e9C966Sfu17c8VBdbNcDra6Rb1VuaF57U8mJSSekWzOyG/NzbG872o9d1T5i/ZCyX4xu2Ljafvuz/ennY2BgeBL8m8bk+La05PjJhuT4vwjJ8Zlxy1NfV+jgj+vUe5cO/hWdev+gQ1+Xnhw/Xgd/pw7+/tTkeI9OvfN0yinS0f/fdPDTdcop0NHnSp1yHtIp5wsd+lk69At06n1Up13SdOynSqfeTTr0E3X4Wa5DL+vQn9LpF2N1ynlCp92f08Fv0in/bh39eHT0uUSH/xt08Kt19DlFh/5POvLW6fBfo1POpzpyFeuUc1BHb7IO/mUdPofo8DNBRw9v6JS/W4dPSaf8Azr9/UooZ6wwSnjaT8edLIYfzvDdgeWqcWtCGsULMsUvYfjBqQzPylnD8NtYvfmjSlT1zlH0c5kaPw/qHQblHGblKzb2w1SKF4LLVePhuwZa7xq/mt7M9LnnUnX5FWm0nA1+dTk3sPIPM3wmuzGHybVcVsv1W6b/DRr+BRifA3K1a+JEHJOnCZK0ss5XLwVkp1+WJEGa2ygtdK/0BGS3v8zrDATcAUGyV5VL1W4/Q1eVl3l99e4q5wqvm95LfkdqkGv9bme1dLt7teSCXzIiXU1OqcbvdkvuJpe7Qfb46gXp5vmVgUKotsGaL2FNAdnvW21bOK/SaXfZyG1fMdzw1AfcftnutdkWVvqqJLwxr1Ke6pJXN7iB0FoANKs81e56oPTItkYgqJSt0yUJ+PCtklYAK06v1+dqpDkD1oIaT321VOPxB2TJV2OrmOeqq6PVTa3xBgO1ShHT+CJczoBMSoAbBf5gveypA2H8fp9/lpXL4AMh3M46hWkXYK2uWqdfkv1OjxwAfkEKKGGFM+BxKdT2KqkqX7JVTpMq5lUWSF6mL1I5KbkYtFznqQdVUhYCZVbUU4DwXVUFBRb3FeipX8mKTVI70S1Vrlzk8QVAtoC70A6KY2IAfhooy+l19yE0ArPK45yAAvlGQ1SdCiMz7qC+pBqZ6vK6nX4b3Jki2YEn+CcTswHRp+QrreALYnNJfmf9SjdUqbTmNNKaYLOyVO9TNyjens41tuZ+lR044+0RERpZWVOsAFOvBxuQXbWc3QJvlZK7rkFeDX2hATqTz+9c6bYxC7VOpVLTJlkRrNFvjwKgQWVLK5uapAa3P+Crd3o9UGxjPlNgnM1ZU1irBEBZ5RIo7nYJSqxWsNOcDQ3u+moiJGCqvRWN0BRyMchOtCijnIsviDvSDoUu0H9iXjAznbyYrX5VHck8ndXO6a4YVEe9g62uTmUscbOkohL9kw4MtBr34StoCMo2F7PSC+sDYKXY2sTgFoDK6nzVbiLffHBHUGmTc4Wn0YrmF/BILvSJEnoc6Nk1PhvvvKwgCeufXiZ0gsaBeLrfDS6hEcTV2LXXXb9SrqXmxuxa2zfLWFecx1tC4apap6xtdtYxsdnR5ddRbw+/VrqgvRCyCtKi+lXYKRa6A8E6N950UbIaH5QhgOJkn1eocftqhJqVbjkguIj68QbwqrSI7G7yyEKdu85V10CShtVCjcvrC7iFOkoPyDpfI3p/rIKNNXVOT72AI4Ewp6xMKsjLF+Y47DPLpCl51sL4zyl5U4WyJUtKZ9ola14BRS9ZAtSFeVarCizmITI/pP+lsFmmEWaXRiGN/Gckv+hfgf1O4/KkQa409jud/BNYvjQCpzE8/jeApSaOPvG/dBjHDUJvWt88ruKq1YNxBvtoujJ/NgqXpdP7+fDvsf94PB1XDX7KcMFRnoHIxRNx+lQSGyhxz5t/vj0NZ9J/YfTOnp8YcUb9IoND9+QacWb9KoPl3EdMKPF7rLweH40f0tm/+MXijTQ2r1auNRy+jMNv4PA2Dv80h7+Owx/m8LM5vBLXIf56VUDbh7+Bn69w+Dl8+Ry+lC8n2IefyaGzGih+ABd7kbiNwxs5fA6HT+Hw+Rw+lZ+ncnh+vaqEw/P6Fzm8iY8TOfxAfn7D4Qfx+uHwgzl8LYcfwuEbOPxQDt/E4TN4e+DwZg7/AIfP5PDrOPwwDr+ew/PzgQ0c/iIO/ySHH8HbG4efxeE3cviRHL6dw1/C4Xdx+CwOv4fDX8rh93P4y3g75PAzOHyEw4/m7Z/Dj+HwPRz+ct6ef9CHv4JDmzg8Px/O5PBjefvn8ON4++fwV/L2z+EtvP1z+PG8/XP4q3j75/ATePvn8PxMpoLD5/L2z+Gv5u2fw0/k7Z/DX8PbP4efxNs/h8/j7Z/DT+btn8Pn8/bP4a28/XN4kbd/Dj+Ft38OX8DbP4cv5O2fw0/l7Z/DT+Ptn8NP5+2fwxfx9s/hi3n75/DX8u3b/KlJDKe13pgtiK3tclokQJDbTdvU09bYVD+QxMbL8Nd8RQn8QrgWb0UPx+AafxvC6LKjewi8AmF01dF2At+MMLro6NMEXogwuuboBgLPRRhdcnQdgWcijK44uobA1yKM7EcbCDwFYXTJ0eUEvhphdMXRCgKPQxhdcLSEwKMQRtcbzSfwcITR5UazCTwIYXS10UwCGxFGFxsVCPz1YoDRtUa7exH+AuFMIj+BjyE8jMhP4I8QHk7kJ/B7CF9E5CfwGwiPIPIT+GWELybyE3grwiOJ/ATehPAlRH4C/wXhLCI/gX+P8KVEfgL/CuFRRH4C/xfClxH5CfwIwqOJ/AR+EOExRH4C/wjhy4n8BP4hwlcQ+c8h7Ec4m8hP4NsQHkvkJ/AKhMcR+Ql8M8JXEvkJvBBhC5GfwHMRHk/kJ/BMhK8i8hP4WoQnEPkJPAXhHCI/ga9GOJfIT+BxCF9N5CfwKIQnEvkJPBzha4j8BB6E8CQiP4GNCOcR+Qn89SKAJxP5vyHtj3A+kZ/AxxC2EvkJ/BHCU4j8BH4P4QIiP4HfQLiQyE/glxGeSuQn8FaEpxH5CbwJ4elEfgL/BeEiIj+Bf49wMZEf4IotqRBhRY7Azy24xrUZwU3d4AUiVhBnyTbrcXto761i6COx+ePuiip7Z3v+khJB7OxovxGTzuVjSoTIPsj+pfkKGMA3xiDrInFSDyRic0+GGDqyyrhs20biQ8BxfLlsC96KHTZfQZbANvZw9B09KUAvhraKHcdmiIY94t6eIGTeRDO/AZnF0E6a/yOWf80NX0P/E4LDFkHOyN0g4LKdaUcBZTi5Df2P2HzDrgogkC+PszBi0ZbuOqgtdCS2Z1n0DshivkKIBmi60SCsuW5bTZ75ihbizxaV3li6uHRRaVWleO+nG8FNbcGutBnD0ogAUouhbTbrKbH1gJwjtj1mieDN5aig0KEItp/YWWZCZwcpCavsoYNcCZvPYgk7xNbjchlm78Y7R0j2zyM/INltJJvY2WJpV1xx6CnLHoKzmdBvds6ykNXTrmwVFfzeowwyhhDQWI87Qs9Y9gNc3npKTrXHZpscIdlSy/GTd5ZJ9DFKNElsW2vpwZsowaZBpO5DEc/ZZGK97wj9xnIYfjrCQSDzWpbbHszjin7zayIqh+kAjD3UaT1Q3hqTp5San93R3LMomGKP7URVYFTvCMUcoVORWqjQ3jmHVAgpqdAROusIA/P28PfEcEHERkq3Ccj2IDE2z2Ru+ZORqoiyydQIqmsnPN5pWS423wUxcMsA8JU7Wyy7cCIRBjW1tAevtMcWmIJj7OEBYltT5Dmcm4jFr5tbd1xEeIrcfyYWQx0C3XxCl66mCw1HutMRCejEthcsaHpi2zOk6sioKxGgyMikqai7TjH8M0oE7E9G9oO5YjhFXeiK4VT9g7BQaNyNrHG3ZMc16jtDms96HMuZMLft+nMkdM0i6JSdZSbSXqzdsqhCPhDDywg/a3gmg+Pw3lLLEq69hp3hjYOYexPoePPrzNw7ziS1C66E13sSOswavoR7kpZw0BG60yKiSWWJ4acon2Fo6uamCDTfH5AmPE0Mz49Y38Buc6yHmJW9GfpzSxaxompLkSPsFsoN3zBKsXMrjtVIfvtprV3mkgJ2oF0eN7eUGFAtNsPzPdAQ9uJOc8slgNmILDpye0TDDpTiAZAChILi3j9Na2+TssTmcwZz62s4oX0w1fJASnSPwJixHhCx6CMoScxmEkNd0XeJVKomJ0Zqbs3IpO0+HBkFO2kX9O0a1GpusYDfJl2gdRT+Cl8nQv9Ki8wkzXco8vKpWIwMVYQVTm4rVICctcsLxE4BxRU7S1g1JayabV0FUIYj9IkYOhbZACVuPMzU0rovExtrGfRQG+upNtZTu6CvOMJeS5Fuh3nGTDtMHvC2JSfO0S8BtL6EHI0139huHtbHSGdJFmMsmzLWIYbWWh7AIP24o+03lnVGZjmypaQGrrg/t6N3AguA2lCEc6eIRSJDxbUR84+aU7Cwd8XcqCN0FHwP0njAHjg1DToV99lTxHALqYq4nk76mypO3T4bEdk1FMYXJQf0UehetWo1BLEoaOIHiIu6w+S47o5MeQy6xzR7aDKMxM2d4LLvMEXxqVQNGW+heR2hHhEsEQZPe2j7c8QwzbM+tBu2mx9pd4Q+FDuiN5h/3GHqEDfG6HWFw2w7XN76MfEg8oQ+vL14u/l+XI8C13GEuI5lxOiuI8yEesXcXjF0Qmz+EOy+Q04TQ7mg7WLoZj8nk4GdwMRnKWJsp2ymZAbSLl/Lo7AJh4phQJvETrJDR2y70SS2iSYyUogwPFWIzb1GO9QROmf+0RNCXL7WlzCnUQwZxE4jzTkTcu2G6kxyphj+IQCrodSZJjpNaTfhHbBIZCG0NbjZHvqs6yZSjaOtwRTdQKl6nqPhwEvypc+h7N3mDhNY0HqoIkyTrgFhU9v3Y6HM1pfuKUbHuAGQkae+jMW6ru6zp/JwHrgJeYI9Vm4KjrWjX+KaNPhjB/iEJSdx/CKrRXbgrbz4dHAXNGWPPfdze/PRHhFGnYryNnlApgM1Df0EWzwDBhows8hlJ9HcIuC/HaGAaW5b6mExVJaJY1+JYuhiGHXYelwMg0XJ2SKyMkrUsuJC9/TaF1Ba81kYlW4H3/Q5RBjRzf+EQswPL0LXoijlJ8BjtAwxF1zOyhhXzgIsZ1EMXdNJB7RY0ZY3YGSI7AKmozXf9KEj90ErRG+ECqPPZNBwRs+zPDCYepa3TuCQfVy2kIa6XNtQ5tY2Qvh55A8n0OJbSB8UQy2EY+zaD8SjL+jALJJMFWMlMCbl4P31XHS2gfTf5SbEP4mTYiLSbyxPC3ToxzIjC6+hABYcsV1De/4aFgTMIEFAcUIQcPFgOhiknaBBgPIYGQdGWiutxVF8xNxCgkQoFFlztN1paSjdjAV1zbtg+/f22T9U3LWsz/4d4ToB26QBlQsxJY5mSy1NGCV9/xrqSzvOzBCvdMAIbni3HI20yrJEDKW+LOeQphinNIWj+DQEOURTn0fGd6N8sywNhMvYNrF5B/TpT4PrUGOo/shFE1Whj9zNhT6WLabhPxQi2d39xT2O8F2CElVuRs9if9HavGqM8bmrjNx4QeYDEFicBsfUYTf/ecg7YmiX/TR47z1iR2SG2PH1JaJhq+jZinRibsdGmu4iUt/7IYPsodTT4BfFe3tLZ5qF4O85xp//nDLezjG+8vN+GN+P3pL4TfB+WRvRrZhz0mbBDBTnO+Zhs7btwT+H8U+3eVjqNuITb5iNFX8odjYLUAOWWEqEnhcecnruxCEn+5cK7sL4MkMcT2DDrrmh1JPz2gqnbUJxsEmeNGLvORG56ypqgwjbw9dbysG3mRwYNX1DQoGdOIRwA8UQMdQtNh+GgeKcXCqGJ88NAyspQ7oujB0wpy6xzQeev9dgvu8ROni0sI4RFFihJy+40JOQ2/Qv5G7ekeko3mFuXRVD5/OxPN4ec1iygpfTgKz0ONr60UjxcdqXn2TPK2ACZKeGYl67rBctYamlYgvCm3GMi+RSi+FsaNVxJU4aJYaydpaYSKDEAqSseIA0xOIIw7wCu2LrSyJEl0vMLcTNtaW+LrYNea0HfXFHFBqmQx4ohl4Wmz8yyGPE8CViaJ/Y0Qv2/Alpb8M+e2zWVzBodILGzxga53D9hQzyL4N6gPojSv0yUL8NNxaYdO40d2aKxZ3B7db20heQaT5eQ2NfHjezp4mZfQJRTeQiC1paC0HZw0XlYRHs7PVSHM2E0i1k607LFYT8GAvWD2NZS+xtHgiXzokdx0HOHWLoM3FjLw1/Zohjd9pDZ0lURMt5rq+w52mJ7xMrdsB8AsoSQXEQRcqWbCw534EhDUxVSuyhKHbPHHvzh70w17G+ZLNCYG0PvV0e+ocDp5gq+RyWWhig7OHbesrD43CkBzMiYduZGY6x7Y6xHaIh4jB8KP6n/fRZEToQGBr+LA/LxyHQ+/OpeWHHEUE0/3lXueG0aHgFUQjZDb1iCpRtb96aaW/u6A3+uBzn6Mcw2shGLkS0gBJHGIWBwCEfo4gcu+GQ3bBbLN4RHAn8Rg/S1uD4dYRecuS+KzZ39DBLATIHunSM+XZhVw6mW9+wtndNsYcLsHOjNGP3iIZu5BrmX1VfIbN77IZ3MHEYvrA3b4PYsscONtZ8xggxtyN0BgCYRPlX1Kyzhy+zh283odtTStrPSlr6AZa0H4YVmpxUlIdEEUYESoK73aLhBE0OQnWZ5cWv2EOn7KHXgxscoePlre3i84rrl6+2x8SsoAW76OByiL9+GoW+G4L5QmdkXZR21KdZRy03/zlWnnsa42+s1tCDvawjOgOCY3HvGVTH6S59f7GbdSnqMHbD2PIl6ks3C7T8abEDrPTeozTLacjyjQiV62aBGPgMPxAZzpBYcy4MY4e/jT3enYEdLUehLiCLYZc9tt1+7zfYc+2h4+a1Bbia1bY+Frtnu3gDITE79ovha0DTxzGazcLpbqY8DqLXzOBoEQZn0gRr7jIJwbRIWpTO1odGYC6Gz6LF0MHI4aMYqqW9W5oN3qUkIobX7wksp3Pga2BYXHNHkSCnPVhW1nUphkxfEOoUoMzfzJayYnvMm7tJcZFnjmEFnZGlWBEOWuhNJ4gxMTM4VgwXIS/D1jQBL4PB9UYaI0i9HzPccRR9e0weZ48tAMbt4RlIO6R0zT2EcUcEnXwsUnWULhkB2XxC9j1GdjchG0/ITkcmHaUrRmQRZt0YmCe2i/dux3XHW0qXli4rvbVUWraND9/MLavBu+mEcNFqgzq2N7d4+6G+MYFa6od6bgL1wn6ob0igtvVDnZ9AXdQP9ZUJ1BP7oR6ZQH15P9QD4V4pW3OEOfiDaRNnZAulD8yanBU1wzjMzWSWfMbNZFo/gbnJ7M9UBMe6OIJqJNjfpSK4/FOOoAwJhnyqIniXr2IcEnSqqxh+kiMwIIFwUkUwiic4fAQITGqCX/IEW5CgTU3wzTGO4BdIcIx1nbFX4vBAZ2jgvaPjUsjaZhcCYvP1FkHOE8OpFtKnLOQX7Vdm/E36VlpkzBHsftdbIpaPuX5I81yO9KFt1C3cQcg/+5iuaZ36B849wX/AEJ2ailHILIiOIZO59asUBaS1ZRKAVfcnUgvkizwDJURfohyTdb+DJBIrN5lb3yLLRpr5YssfBa0ZNQu6ZtT1A1TIMKNKQWQN8BxaI6nmpIGta6qqeTvBWv/Qj7U+Dvf6Zm1D4+2E+sFp1e6P+GmVMpXaBX4m+hph7k7L8i1o6xH5Y1zH3I7DHc6QyOInzK3DDREI30dgVkRH2j6i/gqBzVfcVCJswieXkXQOLeIyfaTliGoRbcdHJIZFX936ImkhWo/1QPQ9sgS3I1pH1tV2cEvj5pabEEeWNhcYE9ZLzS2fpmiVtTVFX1l/pK0d3Y+CtHwI7f/yGfhjP4eS71Q4UteQk66tAZfA9WpwGZM3x8qP6Gg240OqJrIEMHM0nfrfSqb+SzTCyTMueNLeV9/pD2k3ef0w7SYwLt6G3aAIuogpKNGfYeHfVt/9H9JuVRRZdpguWivrGrcR4ar/ncKNYsJ9cUi7JIIPDHDJB0MKMdQVvIythSve4+nDNOfGQ9g7zsXH3ayRAnkAt4Y00w5isUiX/yFtttqPkB4fPoV2spufRy5CA6ozoUlRJI76vVBDnOIEANHTxLqBM7C8eMHv4J23e9mSfMLtjXh7Vi/1ss+PwQI6I38dw9mW+eGHU+jTG6KSAZjhLmrejJfPI/7DJAIxt3yNBh6bD50IH9BrV8xaLkroRNF+TPwtY1/nFUMpvL/QPskhi+CqZm9QNftcvWYvStbsVx6ijXf2A/XjsOjUXm684jJ8cRBXYVMtJbeUENeHDxA2E19XS4x0IthKcBLKkkW8FgSUbS+k4u/wM6kYfjTvNkRehFq7roQmjg4wUCMJH6R9mGSC2WRoayRykA6R2QbqZHEmHvnrIZUD3P4BeU4EkaO5dYyB6hDpYKoYLTYQK4LQ9hfTssmCI+Vo6P+dxiLd0FrCGMqNlWRiQAwF1Gr81b/Ur7YyxWIFDaTlXrAsQUlWH6ISNyBw/UG6iFEFacnfDMRL9wqKl/5SSOKl30kYOf+oP3JG1wt9yrGHBiBHmcqApHkmnGBgNLRT1/VlP3UdEpL767+/T6Pzhw9Av3r+6+T29cj71CBvA6KSluOyCdVSDkrE9bDD5Kn7x+aWv+NyRcxhAeU8RVYuIAz6d7VY5vu0LSLv0ZY7rHSJmTrj0KEDZAJVVKiystLC/0UrW3pAx8ou+oCzsn0HVM8F73+POGZcMz0ul5NHg7b4s7YtZJHsN++zDQHkGRP4fwgjhzhC5NFKqj02B5EmyMIeI9rYY8SIHRdXsVeyAHBBPABU7wVo+XuCFbf1E//dQfozndOmRea8yw0L771HJpDmlr99g34ZK/wD/tJWuNOorfBn/fjl+3Wa/NN36Xx0+37qDRvAG27OhD+bhBtLBLSer4lyvZblfaPbocjU9+g4vv9/bhxf+C7tP1fvpxaxPz6O/4xud/mfqfbAflrtX9+h1e7hqmWP1HEdAKodG3+Ufpqxeg/Lo+y5YdtHSGy1vC+2Wv7vjK0m7qex1fKI4R0azdUKwcGO0FdoS7vfpbOmWlL5DfSnpvK5qsotepUPZ0Xe8W5yd/frdygftZHV+9CkCPH8d0nsbD0ePXkmeTbvO9T+ZkGm6DYgqlGvL6r2W5kGoM+Hkq+3lOJCkLnl3VTsindlbk6FuYb1jedwJS5SRBTRA11oeppqg5a0r29dXG9HQweZiYZMMPB2DaxZZ7+3k2zrUp6J32NvSx0g3hBLwTKh8lKz4zSZDIYzxTacOF4HdUAN5pYfCaq6//G2MsN5kTxmzwGDEdtkmIfiNjGYRkT+Y1/ibheyH4fOjEOfRRZgW4OLu5o80rUkzA5bX2VByKm3QJHkeTnlrShiAZ0AV63FJD5LtTjC+WT+VhuBAslitmie/0FzU4/QNBiHtu3vkFAQZ4Amsc0xJvbgaBMnzcVvK5seSl8g4kw0b36TbAuD6nGbWDdKtOBtsmNNtfXBHvq0PPQ5V9TLb2kUs3kP3f6DiunBYpreTqoYfJ4khm+M4Aaz8rb6iP26xZGgGTeIDdhHhH1sW5eRbK2Rs4jChrPNKTtgNgVK2vsmfQozgIy/8sUtB8pD57om1Wj2h6gHZCAJzkS3+CjkbjmAi5Qmc8s+fPR8kD7P74lvLKwlRtNdau5Ih9E0FYw3TJOuG1V9robvc4SMJl1VKrLlemTzS8PpbWKsNJQBQj88lj4yxR6Gu7Yjg97ChaOYatHmOvaUnRBEQZJorprg7+c4gl1I8FuydwiUce927Ibc8iMOZbh0QZwyWbrYKSRbupiRMGBdrBmwOKGiAtmxs7PrLm5S1XU7Pwb9N2u/W0j7Bau0TWVu+SIh2ttl0K/xr4a+yRqW//03mcThLHT6HuL0XRcw1vBtpPXdRLG+N+i4MWcvq6mTPVM5HRkBrUZXXr5+g/aPzhRlpoJn29CZyuY3aVBEMEeh22zCjdmRVW/Q1stJpROOrFRcT3hTNeGo3Ns34biFTdqQDiccq3BfK6ngroTKH0hTKi9llRPMAFzruYTwu5dWvi6NVr4G0siON1SV79vTV/kcVjnSYeVJFkmIsmbupbPtUZA3Wp04qSNEY/bSkPer14FoBhB1YZNGV8RnUEtzaWybTVYFh7pz+2JbgoLRG7WmxLYNqdoVn/9OiPPuF3RtqitIa/0kh9aKqoJaP8/pq5WgcKtYWl+t+9M0EfU9KiO7Sa+2OclUMmgPDUpQLCWiXo4G0bGXtl8TAi1A1fW9ZPlffp3mRwaV/LuwTe9l+Q8jMGsPNeWlLK3eQ6dIjr10+wyaFpuu4c/znK79OUHZrf0oO6CYEasIf55nRa8meIpf9eMp2gzJTfSXu8n8qecqlY0ZJlyYjf1LLmX0bp3WfvN1rrUf362aP8157VvnT9Wv/3PzJzFURqdP1UZl+nSzMcn06YaEweGifgaHXqgleq9OK1z6GmkF/3hVn7tj/AX2uX+lFR5/VafPlO/m+kzma6pW6HjlW1vh4Gv/YisMMSitYDQkaYUjCf3tef3+Fn1CYF5Vmcfe8zI3jx3+KpvHHjmrzGMPnE0yj/19Qp1r+unj9cnUPeEVOomIvYRqT9mAc9jlN5cIXdckoz7zMqXeS6nVM170XaZXkw8u7SzjesgYNZ8l74eULq4Umz/Nsod67eFbszFOmEjihPEJW/V+z16XuPklnGnPzqbR5a1Z/eX5CctzFc2TxfJk9penheX5YhfJQ4Pu8OWYZRzJMjo+b53xCnXWnbviG1LF5u1Zt5TeqnqmLC/qaw2HJTUM/7rsKoLv8wRDgGBIl01FMJ8nGAEEI7pmcuHmx7iY3VZoiSxD1e7rVcWiZ8lN2WKKzMC7n6rvDovRu5mRsXjXGCNTyGTzx+ZPRXvodZzRZIuhvTCPtIe+AQO9uwifgJXQwCsint4jGjochjNsX01MzN2Le3KKcItUG6ZtQCyaF3R0TcV85N3QzXRD0WeiYbfD0Iu7NmjOfbgZKAez5WC2fNEswvQyi+vzr3XCjPT4ee1o38GeA1xjwZ0GpAIIzOJ7tcXibeb7/2Zg79uE8QnHLkduN3mHqnh/oAEfJWQC3kR3Fl5kD70qtl3/AdnVff9LaNgf2kPbHbkn5BF0q7s9tNsR+iLyCrl3Quw4kxLfhAG3Io/uJHiy9T+IW8Z2g2OCqeKQg+iYukykPtwx33rA/NAAwpfbBPPp4lflyzBqTy0HSezN24HQbYruxt1UZH83qJ1yDfHhJrZ5/Wu7odP8SLu4KS5s6B3cZ/7IVtNWh9mGboZu0IJOwW1e7zTfj0YQf+9lwy72JI8oyCTmnhBDr4kd51LoTqUeh6FbTnGEctD/DiMvBLxsD30ZKe5EST8pb6v+zCS2npLByZ6OPLYDBxloEAdIjyLMaxvSi5LjhiWYFGaXG86JsVfMDw8GXroGRT6GQqL+GF2OyYReJnIzqK4RRFtbbsfdzV9vB8rpvWxSfFzOgTlVVnBcn5e9dAcNhIftUErrZFvHDkU+6KQrKEnsvwJ8VHn4e8QlP0nXMrPMrb8g3uEKe9hnEou75MbSF8iW4CJV770osf9zw94E0nN/Ddx0jV7nCE/Enb/jyF7e0X17eY8G/4gPnZZtJz6XepptUOUHwdegerRIE/J/w3bqYqdu5z2SidNVwvrQYlwZWkMC/F6ypJGFDhsXpeNvqN2Imir+GUHKQ2AGi+Tg5ZZtE9uWWkxkOoN0PrDpzXfgNCqXYSbtoE/EyBQQPSfuQCCPgu5MNYXl1Bx8CLQRRc9C8odQvDZcMgkdxCc/nwG8s8WyCqqbQPHAGkLEsiOvb1cmeRfvoKZJF4SutxD7wucnoFoMo3dsQz+xGU/j2IRHmyHOuYPaSDjt/tHZAt0FHB766GglznGkmtBDZdIIZ5ZlyfmGN3cayHiLSUJ404TL73/fRrcNZNLY5k6LGJF3UMmXR67dTgeVhZS9rmWEx/N/rPGttRdvIw9UzC3GGJ1j9AAi+lUvGY8rxdDZ+Gz1DlPkG/JO5qFbotu2Jb3/Pr0f+c02Rvd8B/aguH1p6Z9i9LJCH+6f/k5GP0uhvwXp4+TrKiLvwZ3Ib7cid+D/oLuGYqWL7aFTpYvsobdLqxxt44WR2cIisW2SCdJKR+4R6wHitJo/NUWC7XRF8PK+/ZjHwAPNgjJiI96HLmaAXh08RvrQMqUTbeP4PbmNvcvPXt03qE5JUZ/TS84/rXY3Tg7I1Z56odHtkn3+a69l5yIJnvpGp9dTne31yG6/05td4/Nne331K3Nys1d55NpsPA0p25p/7QSBP7nq2mvxIClfPUBBl5xdH/R6s+t9cjYpS8gepCEOBFfAT8E+eUG2rwGqwYOUsuF/cnBRdXaNx+sW/BOF2ZBmj0WSesIHHmgH+YUyX9BbXT9BZneQSn1ewXzrFGmOY8HMUockzZesRQ2r5Vpfvcc1Fc+OCljzFzu9QbcNj3qynQ99QaXsrK/G471Ylv7pi23K4VC28+OnYCYolc+Uyc7N2XNTieo8nvj5Iez+BnZfuLkk6f0Gdj9b534Ju1+iud8/v9PtCzjdnYd802z1jR6/r77OXS9rcqr5efrm5Pwo99cwfLfmfvxS8DcyuVmqPV8yXu4tavqKb6Ffril/jYbecFnKdWvZWTv7X4jF8GnXA9C590N3/B2kOGKvB9eBQeGTkFZAmnU0FnsAXz49GYu1Q7rkq1jsMKY9QAf5is4AHc6rYaqC25LwvWl8P2w9pPhywS5I2yE1gY/qhrQJ0iJ2GJJyJo/hhwsFQ1Om4bIhA0zrDAMyR7Dzbs5sicX4c1qS09OzZZC+5/lY7GksOyNzdkbWXPPgVaY1woxR111dYBnH50/R5FfqawId8OcrjY7TVzhIjgEpeGRmipKvkJ1rUwH5nOMFIXWIVCKUZmTOzMiamZE9MyNnZkZ+aUbRnIzutOYBa9Pb0h5KfTjlPiPJtxR1fyQW+/kQyPfC8uT52jNU+ZCf7WhfJ2Kxx9BZzszILM3ImpWR35zykJHy8wz2K2irk3jC12POZOXOylhjSOBnNJRXdCoW20teP0jIU5pRospCLpTdAvkOQ76hWF8kXl9pRvacjA0pzakPATXqF4faXWAzY1j5zUaqd5RjD+DHa/BP4SicBL8d5T6TiH8fbfbFWGwswyvnpBfC/UygdwtUXw8bbRlZD6XYMrLbUm0ZOWvTxIz8+9LFjKLmAeUZJV6UFOTNIbKDBkAWEyn/TmbrRk2fi6X8rnnNGiFlQwoe33GxYja3MSALAZwZ4GEnp9AKgwZ6SNUUvFNqpGSNeDbKYiPtmncj8Am7cwiBUSkUqMI8SxlQj8BTKfQIrjYADPvYua4/RmBcKiXbjGTTAfg/yvCKq1B4dsyES4DsDAMm47p6bzo9eKwCFwEaB9LSRATaBtJ6fomH2EwfTM8bO4F5Lh9K65mBwBozPZFqFgKPgphOJEMRvgRgnHKo2chL6UFCp/DO0UtppYTsU/hzTDkrbd8YysHFeNJLxuX0cKwmBMrhj1sh+8tYepyZiOr9eBzNM2U8U/jtRlV0EUt5814hZQ8B3lMa8T3WWj488gd3X6N0v8byZQacQ+B3BnrOlxHJcOss5jEjgGdimBR+MtmxwSXoS1BmPMhlLgLz07gDvpTT32finV8ysnYEXgHg70ppPxpIpRuFf0yDKbABzwoaDn/Chrgd7hFS5mNvRF0+j0LnAvCRUttgIxXkt3gHlz3l+CnrRnoqFcnzrJE7Oo+WSb4UoKDwB27kjSHQwZ/D9iY7bO4XyNEhdqLYrw2MNsMgfHd9d313fXd9d313fXd9d313fXd9d/3/dGWPYetb7DtuwpiSftdplfTLNDXcq4EvY4sqyhnStVm0XOXs6MIlFFbOSla+I6ackaycDT2KpRF2X1mfUc6+/qo35sN0vZGWp0w39w+kcHxtJ4XCyhnYn7AbytnXylnOF2v0Ez/Dm52zrMwsG9LU61PK5+CUs6J7hpeo8N3DSlR8m5iiBmrq741ReSoYfYzBCh/dDN6cWfK/aifx79hpridYuz7L0p0s3cfST1h6iqXp7Ps2I1l6FUunsXQ2SxeztIaljSy9j6WPs/QJlj7L0p0s3cfST1h6iqXpbF10JEuvYuk0ls5m6WKW1rC0kaX3sfRxlj7B0mdZupOl+1j6CUtPsTSdfX9nJEuvYuk0ls5m6WKW1rC0kaX3sfRxlj7B0mdZupOl+1j6CUtPsTSd9fORLL2KpdNGJ7enOWVl12bnLFoRrJeD2YV5RXmFk6YECWS921qYl1+YV5hL8QIjcnmd9SuzG93+AD5CKcibmpc/qZBmmXK37A8G5NVTsnNk58rA5IU2h6200iYVTM2fXIOfycjNzsGnOdX45MXhWFxOs+cKQl5gdZ3sXAGp7KdprfLLUy+7/Q1CXr1PdueVzrRPgqIZtLI+mLci6PFWT/JUCwSqdQZqhbzq1fVQHk1lP73DGFYBEtzzu71OJGS/GrwyVumBv7K7Cf4C3x6456t2yk4hz10r1fiddW6pttrfB0GhLhf7RIkkk88hkTIkp9/vXE3LUH7f5vITxpx1Hhfk88nkD62X1rEiEBDyXL46fHbxL/fry5jPVvxa3/c11evh2vFAua4U1N9A6Pt+JRtfNPSpGtiqyS+z/DK33txfflzvPQU+UcmvjAPrGaKa4dM044ZyzWdjgFEzTigOdz8bJ9KZ7CaNv17MSI2acWf/QPU4o6e/W5mPV/Irfn0zGwAf0fCv+YyocDsbMxRYGTcq2EcUNgh9/Kckkf+HTKdGzTjVPUw9Tmn1p8jfosmvjHs9w9XjZBqLBbT5HxL6vrnKxwm1WerxX6/9Q5r861j+dSz/0ylq+kxN+pgmvxIHlTDD/+K65PmV6780+ZW4pnCJenzX43+Dpv+VsPwlLH9TSv/1P6nJ3/cdWAqv/Zb6n9XkF5eWsJTC2zUPP7T2067Jj4/DaErh/JT+639DoM8iUjRxoPKdWa282vrx5Rgzl1+JEyN1yem18DHGfzy+Yvm7zzP/51zf4uMk5TvAimLSNfkVuXo09Svf3enx9V+/kp7T5FfiVLJij3ow9J8/3aDOH2HfZYj84Pz0P4Q9LInXz77f08PymzTtrx0PhrH687XxJst/n874o6TDBPV3dpTrbj/zH4b+/S9vu/y15A7W/9jHa8gTqCT+a6BO/XsepOn9w/qvv78rBaiV8ViNN8bHWTU+JT5+qvGp8XFRjU/rG+9U+PT4OKbGD0g670gBrSjjjho/MD6eqPGD4uOEGj847v/V+CFxv67GD+2bt6rwGXE/rMab4/5Vjc+M+001fljcH6rxw+N+To2/KO6/1PgRcb+kxl8c9zdq/Mik860UmF0q/kGNz+rr9yr8pfH+rMb3ffdUjb8sAWcgPvtETIun38ZJ1MP3GB63N/BXBcPj9gT+WsHwEQ1eJv2yr32VbxKtZfjM71P8SdZ5NxNeRwlpmu+tHmf0yr4Y5dtDeGAD4rM1+IUMr+ynUb61dB/DNyyg+MdYBU8zfIWmnA8YPrOK4vcq8a6R4vfMpPifswWSfQzfzeiHKt9RT6FypWrkyiR4c3z/j+KPShhe0OADDF+iwT/B8N0a/PsMr+xHUvCmVIrP1tBPY3hl/5by7aQahlf2jSnfQvpPhm/Q4F9leGXflfJtI2MaxSv7rXIYPo/hlX1nyt6hpQy/7hY1/VqGz9fgtzD8cg2+Ky25/Z8i9In9NyWdtuM6jV/KYvh2DX4iw2vX3UrTabsbNO1eQfCJ/mQVKydbU04zoU/0S3py/YrQDxNMmn79dHpyeQUd//ACoU/0S2+QQOiiBP7/wfBaPk+RchL9IW7ayk7i3wYNSP7d6Fwd/CId/BqCHyrks/FCiRHWMbxT044/GZD8e9L7dMo/q4O/0pT8O+VTdPCzTcnLuVkHv0oH/yTBJ46bf9Khf1MHf1QH/7UO/tKByfE2HXzNQKr/ijHq9d1mHfqf6+B36uBPAH6ccajwNPPnyvqwaVDy73bPG5S8nFsHJf+ed/Og5O34y0EYy/bFJ8o86U865b+mgz+kgx8yODk+e3Byfq4djLF/Yv+ao1NOYHDy76av16HvGJz8u+ZHByf/vvsgGCeHGS8VejT8jBySvPxpQ5J/H71ch/42Vn63pvxVOvThIdQO25mduBn+pzr0PTr4oUOTf7d+4tDk9OVDkWZUgh5u0qGXWfnKd1LZsoLwOx36l3Twn+ngzRnJ8fkZye3KptBrvkN/u0459+jgH9XBv6+D/0wHn26m+jQF1focbE5OX6GDrzZTPSvfnVX8/y906LebmX3Kan9yUod+WCbtj9p2z8qk9Bs0+izOTF7Owzr4X+ngN+vg9+ngv8ykcgmauCVjWHL6CTr4uTr4ZTr4O4fR/ricjQtOFojfS/BJ5pWT/T6fPLlhtVN2+ard/skNft8Kr7suMNm50pVfUDS5bDJ+kTrP1dBAPkjNL95bEzBTEjBTEzDThfgLCYHgCskuxcuXbtZ7W8FqlSR8gCF76iVpKvnCvc3r9Z5vDkfhfF89/e78eb9+Miuffjr8Qt4P+afyTDmPPIX4Js15USpvgHwbK0HZ4wV5A7VOv7ta8rtr7JXyNPrGkX1+Zb5ESysIyH78HHzlVMlmsykMzDsfnROWp9cE67HIInw/yOupd7u89rkL+8onRDYsusrlDfj7KckWLyLQgKTAWbVteo3Pv8rpr7ZXSbaaBsJiw4LKYqk/JvsEczV6iTyVsqNIkjw+8jRLurnKfiHvKJ0HvfYdovPJonmt6TyyJHmT59tz9b0v9O20xWoRKi9QS5UXrqXKC9dS5T+lpcoL0FLlBWlp8QVqafGFa2nx+TLv8ssBOVhTk+cSJGlu2ULJYa+skiQBvL57pScgu/2SXCe5vOAqA0ISlCRV+6SVXt8Kp1eqhk4dkJzBJsHlq2vwumV3dd604qIpyYmkvge7Eijev1qgD4erg3V1qyELB0l9z4MZqSTNXlhabpNs82cBs5Rz9ptJvWD27EpblVRVOtNhQwpVEdVqREB2+qGXz7ppfmm5vUzAJ8kK7ub5lYFpzoYGyGOrmOeqKymZ47DPLFuyRCrIKyQupRIMCESplrzOgCzV+2TJV0NIE2gr5Sn5kiTX+n2rJK+7fqVcK7mxFYBYQyp5PStckisQJEoS4sxULa6UrVP5lzNXBGvsLkBaXeC0Jdnv9MgBuwvds8tmS2TAOk1hYIWzWnIBx40JElX6iqVyUE/A7ZftXpttYaWvSlJR5RUDiyvrfPWUMdT63EZpIbOOMlBEAE3j5mpvRZLiA9PZy6u2ZNqUp7rQRIF9awGwscpT7a4nbWVTF5VntQpMO1CmXOTxBSTcHlFoB9oyq4ZaqHN6vT5FzdKUvCl5U4UafB9VjWKap2JhDKK5jewXgqQNxfgCLYw+MkhRt3Ae0bdWmvpVeEcuBpsgKpcTxbUWShJ2TYheSHUFdb5qFxmBJFeTU4LimzxyIg+ytcAfrJc90EGIBYG8UFOgP4PzBdEwJRImJTE4sjEFDMLrlaAJ6zz1UDUaXBXUVUwNzkctDv66nXXna3Q1K91yIIkA6vaaldBekr2qXOpzQlXlZehvqsj2EMm+QCJvQ0vBgLuaNgpooM6VtB1q/G53AgPYa6eTXlvj8ffbbUFcb4KVIHPJWZO0zoNYizVfQmmgLN9qm461oO0XuxUvXriq1inbGpO6mwKOcT1fE6/ZCobKWtSbUGeVPcGUtIYB4imelekZ6tMRoVIudIGdJaKL4zallUiqDvikWhixQXm4acnnTdoh0RWyUIw6MR81Q8VNJbFG8FsgW5/potHCeJAv2SqnSRXzKgskr9ap1bnr6nyNCdaCWuprGa106OT67ebSikCAswjf1BpvMFCb2LY4aOdjv29yrvA0WrHrBjzYMSE7ukSQtcYHOoccpTPtkjWvQNOVMBRP6NfoRdD1ge4lTgZtIX3y6ZWC/UivBKkBRIdQXLrdvZq5xaR+KrGfg8pddQ1qjbuS+GrKJG1NkDdpg091ed1OmJrIEPvYQSfwTwZONO7A7avRmhiKR9pOLRWJE0i/vIAxl8yONELWkIMSEsxKPZiDfeoUnGwcn86P40RfjXouAAypUnLXNcirwWc1QFU+vxOmysnaeAX4tHoYBWRXrUYVZHcdDPpNTVKD2x/wgTfxQIGN+YmmdIHjBXgUtBPSYgtgQIYR0J1kJE0iHRv1EpzfovpV6CAXugPBOiyqrAzw+ZS5adgVYNqcOOCAVqezLpwkJCpoCMo2VxImwNbKIZpz3g5eDCYdScy7YXVfy1sL1SFl4qiNUYBAfd3/A6N3xntXnAAA'
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
import numpy as np
i8 = np.int64
i4 = np.int32
mod = 998244353

def solve(a, w):
    res = 0
    b = np.zeros(w.shape[0], i8)
    for c in a:
        b[c] += 1

    for i in range(1, w.shape[0]):
        s = 0
        t = 0
        for j in range(i, w.shape[0], i):
            s += b[j] * (j // i)
            t += (b[j] * (j // i) * (j // i))
        u = ((((s ** 2 - t) // 2) % mod * i) % mod) * i % mod
        res = (res + w[i] * u % mod) % mod
    return res % mod

def mod_inverse(inv):
    inv[1] = 1
    for i in range(2, inv.shape[0]):
        inv[i] = mod - (mod // i) * inv[mod % i] % mod

def calc_w(w, inv):
    for i in range(2, w.shape[0]):
        w[i] = (inv[i] - w[i]) % mod
        for j in range(i * 2, w.shape[0], i):
            w[j] = (w[j] + w[i]) % mod

def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    A = np.empty(N, i8)
    for i, c in enumerate(stdin.readline().split()):
        A[i] = int(c)
    v = 10 ** 6
    inv = np.empty(v + 1, i8)
    mod_inverse(inv)
    w = np.ones(v + 1, i8)
    calc_w(w, inv)
    ans = solve(A, w)
    print(ans)
'''