24292번 - РАЗДЕЛЯЙ и ВЛАДЕЙ 다국어

Сашка тайно извадила телефона си в час по музика и отворила програма, която генерира случайни двойки числа. Така тя генерирала Q двойки числа, всяко от които е не поголямо от N. Тя може да прилага следните две операции върху една двойка числа:

1. За двойката (a, b) избира число d, което е делител на a. Изтрива двойката (a, b) и на нейно място записва (a/d, b × d).
2. За двойката (a, b) избира число d, което e делител на b. Изтрива двойката (a, b) и на нейно място записва (a × d, b/d).

Сашка може да прилага тези две операции неограничен брой пъти, само за числа от една и съща двойка. Тя иска след краен брой операции, числата във всяка двойка да имат възможно по-голям най-голям общ делител (НОД). Напишете програма divide, която намира възможно най-големия най-голям общ делител, който може да се постигне за всяка една двойка числа.

На първия ред от стандартния вход са дадени две цели, положителни числа N и Q – най-голямата възможна стойност за число от всички двойки и броят на двойките.

На i-тия ред от следващите Q реда от стандартния вход са дадени по две цели, положителни числа ai и bi , съответно числата от i-тата двойка.

На стандартния изход на един ред отпечатайте Q числа, като i-тото от тях е максималният възможен НОД, който може да бъде постигнат за i-тата двойка числа.

• 1 ≤ N ≤ 2 × 10⁶
• 1 ≤ Q ≤ 500 000
• 1 ≤ a_i, b_i ≤ N

Пример №1

1. (2,8) → (4,4)
2. (6,72) → (36,12)
3. Числата не се променят.

Пример №2

1. (2,32) → (8,8)
2. (9,8) → (3,24) → (6,12)