$10^7$ 内好时机个数不会多于 $10^7$，所以欧拉筛预处理后爆搜求出所有好时机，一旦当前乘积大于 $10^7$ 就跳出。因为每个数分解质因数后结果唯一，所以每次搜索都是有效的，总时间复杂度是对的。

每次询问求一下前缀和即可，记得开 $\text{long long}$。

质数数量很多，但最多只有 $8$ 个质数被选，爆搜时注意一下栈空间即可。