SP19975 APS2 - Amazing Prime Sequence (hard)

This problem is a harder version of [APS](../APS). Let $ f(n) $ be the smallest prime factor of $ n $ . For example, $ f(2) = 2,\ f(4) = 2 $ and $ f(35) = 5 $ . The sequence $ S(n) $ is defined for all positive integers as follows: \- $ S(1) = 0 $ \- $ S(n) = S(n-1) + f(n) $ (if $ n \ge 2 $ ) Given $ N $ , find $ S(N) $ **modulo** $ 2^{64} $ .

First line contains $ T $ ( $ 1 \le T \le 10000 $ ), the number of test cases. Each of the next $ T $ lines contains a single integer $ N $ . ( $ 1 \le N \le 1234567891011 $ )

For each integer $ N $ , output a single line containing $ S(N) $ **modulo** $ 2^{64} $ .

- Input #0: $1\le T\le 10^4,1\le N \le 10^4$，TL = 1s. - Input #1: $1\le T\le 1000,1\le N \le 10^8$，TL = 20s. - Input #2: $1\le T\le 200,1\le N \le 10^9$，TL = 20s. - Input #3: $1\le T\le 40,1\le N \le 10^{10}$，TL = 20s. - Input #4: $1\le T\le 7,1\le N \le 10^{11}$，TL = 20s. - Input #5: $T=1,1\le N \le 1234567891011$，TL = 20s. #### Source Limit is 8 KB.