我們摯愛的一二學術長檸檬，於西元2023年1月13日，悄悄的離開這個世界，我們痛徹心扉，就僅僅一眨眼的時間，天人永隔。檸檬安祥的走完了18年的人生旅程，他彷彿在沉睡中做了一個美夢。夢醒了，留下陪伴我們成長過程中的點點滴滴，留下我們永恆的追思與感恩。

身為高三生，檸檬不負眾望地被學測給揍爛。
然而他們不知道的是，在學測前一天，檸檬做了一個惡夢：

進到考場後，第一個考科是數學。
檸檬非常緊張，因為數學正好是他最爛的科目。
發下考卷後，發現考卷上只有一個題目，
檸檬看著題目，發現自己完全不會算QAQ
很快收卷的鈴聲敲響，檸檬交了一張白卷。

夢醒了，做了惡夢的檸檬在學測考試時一直想著那道數學題到底要怎麼解，結果學測就燒雞ㄌ。

田鼠博士為了幫助可憐的學測牲檸檬，發明了一台機器「夢境終結者」，用來進入學測前檸檬的夢境幫他解決數學問題！該問題如下：

給定非負整數$k$、長度為$n$的序列$a$，

定義函數$\sigma_k(x) = \displaystyle\sum_{d|x}{d ^ k}$，也就是$x$的所有正因數的$k$次方和。

另一函數$\omega(x) = \displaystyle\sum_{p|x}1$，其中$p$為質數，也就是$x$的相異質因數個數。
對於區間$[l, r]$，請解出$\displaystyle\sum ^ {r}_{i = l}{(\ \omega(a_i)\times\sigma_k(a_i)\ )}$的值。

有了早已取得數學博士學位的田鼠博士的協助，你們很快便解決了問題。
然而，惡夢還沒有結束：

夢裡的題目慢慢出現了變化，
「糟糕了，是修改操作！」田鼠博士大喊。
每當你解出題目，題目便會將序列$a$的第$i$項$a_i$乘上一個與$a_i$互質的整數$t$。
「現在你必須加快動作，數字已經越來越大了...。」

作為建北電資學術力擔當的你，請你寫出一個程式來自動計算數學題，拯救可憐的學測牲吧。