Masala #0745

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 20 %
3.9 (Baholar 7)
14

  

Tub ko'paytuvchilar tarkibi

Sizga N=P1A1P2A2PxAxN = P_1^{A_1} * P_2^{A_2} * \dots * P_x^{A_x}  soni berilgan. Bu yerda PP tub sonlardan tashkil topgan massiv (hech bir elementi takrorlanmaydi), AA natural sonlardan tashkil topgan massiv. Sizning vazifangiz tub ko’paytuvchilari tarkibiga NN sonining tub ko’paytuvchilari tarkibidagi barcha tub sonlar qatnashgan hamda NN sonining bo’luvchisi bo’la oladigan natural sonlar yig’indisini chop eting.


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, T(1T10)T (1 \le T \le 10) testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun birinchi qatorda X(1X100000)X (1 \le X \le 100000) NN sonining tub ko’paytuvchilari tarkibida nechta tub son ishtirok etgani kiritiladi. Ikkinchi satrda bo’sh joy bilan ajratilgan holda NN ta natural son, P(0<Pi<106)P (0 < P_i < 10^6) tub sonlar ro’yxati kiritiladi. Uchinchi satrda bo’sh joy bilan ajratilgan holda NN ta natural son, A(1Ai109)A (1 \le A_i \le 10^9) massiv elementlari kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida satrda masala javobini 109+710^9+7 ga bo’lgandagi qoldiqni chop eting


Misollar
# input.txt output.txt
1
1
3
2 3 5
2 1 1
90
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin