나누고 소유하라

Сашка는 음악 시간에 몰래 휴대폰을 꺼내 무작위로 두 수의 쌍을 생성하는 프로그램을 열었다. 그렇게 해서 만들어진 Q개의 쌍은 각 수가 N 이하이다. 그녀는 한 쌍의 두 수에 다음 두 연산을 적용할 수 있다.

1. 쌍 (a, b)에 대해 a의 약수 d를 고른다. 쌍 (a, b)를 지우고 그 자리에 (a/d, b × d)를 적는다.
2. 쌍 (a, b)에 대해 b의 약수 d를 고른다. 쌍 (a, b)를 지우고 그 자리에 (a × d, b/d)를 적는다.

Сашка는 같은 쌍의 두 수에 대해서만 이 두 연산을 횟수 제한 없이 적용할 수 있다. 그녀는 유한 번의 연산 뒤에 각 쌍의 두 수가 최대한 큰 최대공약수(НОД)를 가지게 하고 싶어 한다. 각 쌍마다 달성할 수 있는 최대공약수 중 가장 큰 값을 구하는 프로그램 divide를 작성하시오.

표준 입력의 첫째 줄에 두 정수 N과 Q가 주어진다. N은 모든 쌍의 수가 가질 수 있는 최댓값이고, Q는 쌍의 개수이다.

다음 Q개 줄의 i번째 줄에는 i번째 쌍의 두 정수 ai와 bi가 주어진다.

표준 출력의 한 줄에 Q개의 수를 출력한다. i번째 수는 i번째 쌍에서 달성할 수 있는 최대공약수의 최댓값이다.

• 1 ≤ N ≤ 2 × 106
• 1 ≤ Q ≤ 500 000
• 1 ≤ ai, bi ≤ 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)