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

Տրված են Q հատ թվազույգեր, որոնցից յուրաքանչյուրը չի գերազանցում N թիվը։ Յուրաքանչյուր թվազույգի համար, մյուսներից անկախ, պետք է գտնել և արտածել մեկ թիվ։ Այդ թիվը ստանալու համար հերթական (a, b) բնական թվերի զույգի հետ կարելի է կատարել հետևյալ գործողությունները․
  1. Ընտրել որևէ d թիվ, այնպիսին, որ a-ն բաժանվում է d-ի վրա առանց մնացորդի և (a, b) զույգը փոխարինել (a/d,b×d) զույգով։
  1. Ընտրել որևէ d թիվ, այնպիսին, որ b-ն բաժանվում է d-ի վրա առանց մնացորդի և (a, b) զույգը փոխարինել (a×d,b/d) զույգով։
Այս երկու գործողություններից յուրաքանչյուրը թույալտրվում է կիրառել որքան ուզեք։ Արդյունքում հնարավոր է ստանալ բազմաթիվ թվազույգեր։ Այդ թվազույգերից յուրաքանչյուրն ունի իր ամենամեծ ընդհանուր բաժանարարը (ԱԸԲ)։ Պահանջվում է պարզել, թե առավելագույնը ինչ ԱԸԲ է հնարավոր ստանալ։

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

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

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

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

Օրինակ

Մուտք
Ելք
100 5 2 8 6 72 38 39 2 32 9 8
4 12 1 8 6

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

  1. (2,8)→(4,4)
  1. (6,72)→(36,12)
  1. Որևէ նոր թվազույգ հնարավոր չէ ստանալ։
  1. (2,32)→(8,8)
  1. (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 միավոր) Լրացուցիչ սահմանափակումներ չկան:

Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in