Cho một số nguyên dương ~D~, ta xây dựng đồ thị sau từ nó như sau:

• Mỗi đỉnh được đánh số là một ước của ~D~;

• Hai đỉnh ~x~ và ~y~ ~(x > y)~ có một cạnh vô hướng giữa chúng nếu ~x~ chia hết cho ~y~ và ~\frac{x}{y}~ là số nguyên tố;

• Trọng số của một cạnh là số ước của ~x~ không phải là ước của ~y~ ~(x > y)~.

Ví dụ đồ thị với ~D = 12~ như sau:

Do ~D = 12~ có các ước là ~\{1, 2, 3, 4, 6, 12\}~ nên đồ thị có ~6~ đỉnh được đánh số là ~1, 2, 3, 4, 6, 12~.

Không có cạnh nào giữa đỉnh ~3~ và đỉnh ~2~, vì ~3~ không chia hết cho ~2~. Không có cạnh nào giữa ~12~ và ~3~, vì ~\frac{12}{3} = 4~ không phải là số nguyên tố.

Giữa hai đỉnh ~12~ và ~4~ có một cạnh vô hướng nối chúng, vì ~12~ chia hết cho ~4~ và ~\frac{12}{4} = 3~ là số nguyên tố. Cạnh ~(12, 4)~ có trọng số là ~3~, vì ~12~ có các ước ~\{1, 2, 3, 4, 6, 12\}~ và ~4~ có ước ~\{1, 2, 4\}~. Như vậy có ~3~ ước của ~12~ không phải là ước của ~4~ là ~3, 6, 12~.

Gọi độ dài đường đi giữa đỉnh ~u~ và ~v~ trong đồ thị là tổng trọng số các cạnh trên đường đi. Ví dụ đường đi ~(1, 2), (2, 6), (6, 12), (12, 4), (4, 2), (2, 6)~ có độ dài ~1 + 2 + 2 + 3 + 1 + 2 = 11~. Đường đi rỗng có độ dài ~0~.

Đường đi ngắn nhất giữa hai đỉnh ~u~ và ~v~ là đường đi có độ dài nhỏ nhất trong số các đường đi giữa đỉnh ~u~ và ~v~.

Hai đường đi khác nhau nếu số cạnh của hai đường đi khác nhau hoặc tồn tại chỉ số ~i~ sao cho cạnh thứ ~i~ của hai đường đi khác nhau.

Bạn được cho ~q~ truy vấn có dạng ~u~ ~v~ là yêu cầu tính số đường đi ngắn nhất giữa hai đỉnh ~u~ và ~v~. Câu trả lời cho mỗi truy vấn có thể lớn, vì vậy hãy đưa ra nó theo mô-đun ~998244353~.

Input

• Dòng đầu tiên chứa số nguyên ~D~ ~(1 \le D \le 10^{15})~ là số mà đồ thị được tạo từ nó.

• Dòng thứ hai chứa số nguyên ~q~ ~(1 \le q \le 3 \cdot 10^5)~ là số truy vấn.

• Mỗi dòng trong ~q~ dòng tiếp theo chứa hai số nguyên ~u~ và ~v~ (~1 \le u, v \le D~; ~u, v~ đều là ước của ~D~) mô tả một truy vấn.

Output

Với mỗi truy vấn, in số đường đi ngắn nhất giữa hai đỉnh đã cho theo mô-đun ~998244353~.

Scoring

Sample Input 1

12
3
4 4
12 1
3 4

Sample Output 1

1
3
1