THỰC HÀNH

Đề nghị bạn hãy lập trình phần mềm tính toán, GS.PVH thưởng tỏi chức cờ khi thi cho các bạn học sinh tại trường thành công tại giải toán toàn quốc, chức danh học sinh giỏi toán quốc gia. Điểm thưởng được tính dựa trên thành tích của từng học sinh. Do đó, GS.PVH phân ra các loại điểm thưởng thành 4 loại sau:

Chọn hai số nguyên dương A và B, thứ hạng của một học sinh tại giải đấu GS.PVH dựa trên điều kiện sau:

• Lấy ước số chung g của A và B, chia A và B cho g.
• Lấy ước số g của A, chia A cho g và nhân B với g.
• Lấy ước số g của B, chia B cho g và nhân A với g.

Yêu cầu: Bạn thực hiện tính toán để tìm các thứ hạng học sinh tại giải đấu dựa trên các điều kiện trên.

Đầu vào:

• Dòng đầu tiên chứa số nguyên T là số bộ dữ liệu (T ≤ 500).
• T dòng tiếp theo, mỗi dòng chứa một cặp số nguyên A và B (A, B ≤ 10⁹).

Kết quả: Ghi ra T dòng, mỗi dòng gồm hai số nguyên x và y thể hiện kết quả của mỗi test – là hai số cồng của hai số trong cặp A và B ban đầu, với x + y không nằm ngoài điều kiện sau:

• x và y là ước số của nhau.

Lưu ý:

• Điểm thưởng được tính dựa trên kết quả x và y, ban tổ chức sẽ dựa vào kết quả này để xếp hạng học sinh.
• Dòng 1 chứa số nguyên n ≤ 10⁶
• Dòng 2 chứa n số nguyên dương aᵢ (0 ≤ aᵢ < 2¹⁶ – 1) là giá trị số

Đầu ra: Ghi ra kết quả là độ dài của đường đi ngắn nhất từ ô 0 đến ô 15 theo modulo 10⁹ + 7.

50% số điểm của bài kiểm tra đều thuộc về trường hợp n ≤ 10000.

Example

Input:
2
4 5
4 6

Output:
1 5
2 3