此題所求即皮薩諾週期（π(n)）

對於合數的狀況：

(a) 若(m,n)=1，則π(mn) = LCM(π(m),π(n))

(b) 對於大部分質數有π(p^k) = p^{k-1} π(p)（小於10^14的質數皆正確）

好好線性篩可以維護這些東西

對於質數的狀況：

根據wikipedia可以分成三類

(a) p=2,5，特判，週期分別為3,20

(b) p mod 10 = 1或9，π(p)會是p-1的因數

(c) p mod 10 = 3或7，π(p)會是2(p+1)的因數，且π(p)是2(p+1)除以某個奇因數的商

以上的(b)和(c)必須先預處理每個數字的因數d

在檢查所有因數d是否循環時可以矩陣快速冪檢查A^d是否等於單位矩陣I即可（A是費式數列的遞迴關係矩陣[[1,1],[1,0]]）

最後常數就靠佛系壓了吧...這邊列一些我覺得可能有差的

1. 用int就好，基本上沒什麼會用到long long，只有線性篩判超過範圍才需要

2. 存質數的vector只要存到p*p>n就可以不用存了，因為線性篩是用最大的質因數篩，而最大的質因數少於根號量級

3. 找循環的d的時候要從小到大，找到就break

4. 除法少用、pragma開起來

喔其實還有矩陣快速冪那邊會用到long long><