question link。

不考虑 $q \le 10^3$ 的情况，可以爆搜。