D. Агуу Мөөгөн Хааны Айлчлал

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Агуу Мөөгөн Хаан одойчууд дээр айлчлан очсон боловч бүх одойчууд бус зөвхөн цөөн хэдэн сонгогдсон одойчууд л хаанд бараалхах эрхтэй болно.

$ХБЕХ(k^{2^l}+1, k^{2^{l+1}}+1, ..., k^{2^r}+1)$ тооны одойчууд хаанд бараалхах эрхтэй ба k, l, r тоонуудыг хаан өөрөө өгдөг болно.

Одой түүхчид Агуу Мөөгөн Хааны айлчлал бүрийг баримтжуулан тэмдэглэглэхээр шийдсэн ба тэдэнд айлчлал бүрийн k, l, r тоонууд ба $p_i$ анхны тоо байгаа бол айлчлал бүрд хаанд бараалхах эрхтэй одойчуудын тоог $p_i$-д хуваасан үлдэгдлийг олж өгнө үү.

Оролт

Эхний мөрөнд хааны нийт айлчлалын тоо болох $t(1<=t<=10^5)$ байрлах ба дараагийн $t$ мөрөнд хоорондоо хоосон зайгаар тусгаарлагдсан бүхэл тоонууд $k_i, l_i, r_i$ ба $p_i(1<=k_i<=10^6, 0<=l<=r<=10^{18}, 2<=p_i<=10^9)$-үүд байх ба $p_i$ болгон нь заавал анхны тоо байна.

Гаралт

Мөр болгонд хаанд бараалхах эрхтэй одойчуудын тоог анхны тоо $p_i$-д хуваасан үлдэгдлийг хэвлэ. Айчлалуудын хариунуудыг оролтонд орж ирсэн дарааллаар нь хэвлэнэ.

Орчуулсан: devman

Жишээ тэстүүд

Оролт
2
3 1 10 2
5 0 4 3
Гаралт
0
0

Тэмдэглэл

We consider that $LCM(a_{1}, a_{2}, ..., a_{n})$ represents the least common multiple of numbers $a_{1}$, $a_{2}$, $...$, $a_{n}$.

We consider that $x^{0} = 1$, for any $x$.

Сэтгэгдлүүдийг ачааллаж байна...