Masala #0MENQLAX9K

Xotira 256 MB Vaqt 1500 ms

Sevimli tub son

Ismoil matematikada tub sonlarda qiynaladi. Ustozi unga yana tub sonlar qatnashgan masala berdi va bu “Sevimli tub son” larni topishga doir ekan. \(A^{P!} (mod\)\(P)\) ifodani hisoblash kerak. A(mod P) degani A%P yoki A ni P ga bo'lgandagi qoldiq.

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤T≤5×10^5)\)

Keyingi T ta qatorda A va P natural sonlar beriladi. \((1≤A≤10^{18})\), \((1≤P≤5×10^6)\)

Chiquvchi ma'lumotlar:

Agar P tub bo'lsa \(A^{P!} (mod\)\(P)\) ni, aks hoolda −1 ni chop eting.

Misollar

#	input.txt	output.txt
1	2 3 2 5 4	1 -1
2	18 393 889 987 699 379 32 950 139 953 788153 361 2484049 313 2916841 542 2515921 558 4525501 159 1289303 65 712 983 918839 908 3431143 258 402 360 4439797 975 470 127 2601787 912 1557481	-1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1 1

input.txt

output.txt

2
3 2
5 4

1
-1

18
393 889
987 699
379 32
950 139
953 788153
361 2484049
313 2916841
542 2515921
558 4525501
159 1289303
65 712
983 918839
908 3431143
258 402
360 4439797
975 470
127 2601787
912 1557481