Fişierul intrare/ieşire:	powerful.in, powerful.out	Sursă	AGM 2019, runda finala
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.7 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Powerful

Amatias e cel mai puternic super erou; intr-adevar, e destul de puternic sa bata oricare adversar intr-o singura lovitura de picior! Pe de alta parte, celelalte federatii de eroi din restul pamantului sunt mai putin puternice. Sunt T federatii. Federatia i se caracterizeaza prin 5 numere diferite: x_i, y_i, a_i, b_i, m_i. Puterea p_i a federatiei se defineste prin ecuatia . Pentru a ne da seama cu cat mai puternic este Amatias fata de diversele federatii, dandu-se x_i, y_i, a_i, b_i, m_i, sa se gaseasca valoarea lui p_i.

Date de intrare

Fişierul de intrare powerful.in va contine pe primul rand T.
Pe urmatoarele T randuri va aparea, pe randul i+1, numerele x_i, y_i, a_i, b_i, m_i.

Date de ieşire

În fişierul de ieşire powerful.out afisati T randuri: valorile lui p_i pentru i = 1, ..., T.

Restricţii

• 1 ≤ T ≤ 100
• 1 ≤ x_i, y_i, a_i, b_i ≤ 10¹⁸
• 1 ≤ m_i ≤ 10.000
• m_i este prim.

Exemplu

Cum se trimit solutii?