Số lượng ước số

Trong một buổi bảo vệ đồ án, FullHouse Dev được giám khảo đưa ra một bài toán thú vị về ước số. Họ cần tính tổng của ước số lớn nhất không chia hết cho một số nguyên tố cho trước của mỗi số trong một dãy số. Với tinh thần quyết tâm, FullHouse Dev đã bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

Cho hai số nguyên \(n\) và \(k\). Với mỗi số trong đoạn \([1, n]\), nhiệm vụ của bạn là tính ước số lớn nhất của số đó mà không chia hết cho \(k\). In ra tổng của các ước số này.

Lưu ý: \(k\) là một số nguyên tố.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Mỗi test case gồm một dòng chứa hai số nguyên \(n\) và \(k\).

OUTPUT FORMAT:

• Với mỗi test case, in ra một số nguyên duy nhất trên một dòng - tổng của các ước số lớn nhất không chia hết cho \(k\).

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq n \leq 10^9\)
• \(2 \leq k \leq 100\)

Ví dụ

INPUT

4
10 3
10 2
10 5
1000000000 97

OUTPUT

41
36
43
494897959532893312

Giải thích

• Ở test case đầu tiên, với \(k = 3\), các ước số lớn nhất không chia hết cho 3 của các số từ 1 đến 10 là: [1, 2, 1, 4, 5, 2, 7, 8, 1, 10]. Tổng của chúng là 41.
• Ở test case thứ hai, với \(k = 2\), các ước số lớn nhất không chia hết cho 2 là: [1, 1, 3, 1, 5, 3, 7, 1, 9, 5]. Tổng là 36.
• Ở test case thứ ba, với \(k = 5\), các ước số lớn nhất không chia hết cho 5 là: [1, 2, 3, 4, 1, 6, 7, 8, 9, 2]. Tổng là 43.