Բաժանիր և բազմապատկիր

Տրված են Q հատ թվազույգեր, որոնցից յուրաքանչյուրը չի գերազանցում N թիվը։ Յուրաքանչյուր թվազույգի համար, մյուսներից անկախ, պետք է գտնել և արտածել մեկ թիվ։ Այդ թիվը ստանալու համար հերթական (a, b) բնական թվերի զույգի հետ կարելի է կատարել հետևյալ գործողությունները․

1. Ընտրել որևէ d թիվ, այնպիսին, որ a-ն բաժանվում է d-ի վրա առանց մնացորդի և (a, b) զույգը փոխարինել (a/d,b×d) զույգով։

2. Ընտրել որևէ d թիվ, այնպիսին, որ b-ն բաժանվում է d-ի վրա առանց մնացորդի և (a, b) զույգը փոխարինել (a×d,b/d) զույգով։

Այս երկու գործողություններից յուրաքանչյուրը թույալտրվում է կիրառել որքան ուզեք։ Արդյունքում հնարավոր է ստանալ բազմաթիվ թվազույգեր։ Այդ թվազույգերից յուրաքանչյուրն ունի իր ամենամեծ ընդհանուր բաժանարարը (ԱԸԲ)։ Պահանջվում է պարզել, թե առավելագույնը ինչ ԱԸԲ է հնարավոր ստանալ։

Մուտքային տվյալներ

Առաջին տողում տրված են N (1 ≤ N ≤ ) և Q (1 ≤ Q ≤ 500 000) դրական ամբողջ թվերը՝ թվազույգերին պատկանող թվերի մեծագույն արժեքը և թվազույգերի քանակը։

Հաջորդ Q տողերից յուրաքանչյուրում տրված են երկու դրական ամբողջ a և b թվեր, որոնք չեն գերազանցում N-ը։

Ելքային տվյալներ

Ելքում պետք է արտածել Q հատ թիվ, որոնցից i-րդը պետք է հավասար լինի մուտքում տրված i-րդ թվազույգից նշված կանոնների կիրառման արդյունքում ստացվող թվազույգերի ԱԸԲ-ներից մեծագույնին։

Օրինակ

Բացատրություն

1. (2,8)→(4,4)

2. (6,72)→(36,12)

3. Որևէ նոր թվազույգ հնարավոր չէ ստանալ։

4. (2,32)→(8,8)

5. (9,8)→(3,24)→(6,12)

Ենթախնդիրներ

• Ենթախնդիր 0 (0 միավոր) Օրինակը,

• Ենթախնդիր 1 (17 միավոր)  որտեղ -ն և -ն պարզ թվեր են։

• Ենթախնդիր 2 (11 միավոր) , որտեղ -ն դրական ամբողջ թիվ է

• Ենթախնդիր 3 (25 միավոր) N ≤ 10 000, Q ≤ 1 000:

• Ենթախնդիր 4 (23 միավոր) N ≤ 100 000, Q ≤ 100 000:

• Ենթախնդիր 5 (24 միավոր) Լրացուցիչ սահմանափակումներ չկան: