Masala #0745

Xotira 16 MB Vaqt 1000 ms
14

Tub ko'paytuvchilar tarkibi

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


Kiruvchi ma'lumotlar:

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

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


Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida satrda masala javobini \(10^9+7\) ga bo’lgandagi qoldiqni chop eting


Misollar
# input.txt output.txt
1
1
3
2 3 5
2 1 1
90