바이트몬 수집가 2

바이타자르는 바이트몬 카드를 아주 많이 모았다. 각 카드에는 바이트몬이 그려져 있고, 진화 전 힘과 진화 후 힘이 적혀 있다. 그는 이 컬렉션을 팔려고 한다. 바이트코비트코 카드 거래 협정에 따르면 컬렉션의 가격은 덱에 있는 모든 바이트몬 힘의 최대공약수(NWD)에 비례한다. 다만 이 협정은 힘이 두 개인 카드를 고려하지 않았다. 그래서 바이타자르는 카드마다 진화 전 힘이나 진화 후 힘 중 하나를 고를 수 있다. 그는 최대공약수가 가장 커지도록 고르려 한다. 그가 팔 수 있는 최고 가격을 구하는 프로그램을 작성하라.

첫째 줄에 정수 $n$ ($1 \le n \le 10^6$)이 주어진다. 바이타자르가 가진 카드의 수다. 이어지는 $n$개 줄에는 두 정수 $a_i$와 $b_i$ ($1 \le a_i \le 5 \cdot 10^5$, $1 \le b_i < 2^{63}$)가 공백 하나로 구분되어 주어진다. 각각 i번째 바이트몬의 진화 전 힘과 진화 후 힘이다. 진화 후 힘은 진화 전 힘보다 작을 수도 있다.

바이타자르가 얻을 수 있는 바이트몬 힘의 최대공약수 중 최댓값을 한 줄에 출력한다.

예시에서 바이타자르는 세 번째와 네 번째 바이트몬은 진화 후 힘을, 첫 번째와 두 번째 바이트몬은 진화 전 힘을 고른다. 그러면 힘은 차례로 5, 10, 20, 5가 되고, 이들의 최대공약수는 5이다.