Hai số nguyên dương \(x\) và \(y\) được gọi là một cặp số bạn bè nếu như chúng có chung tập các ước nguyên tố. Ví dụ: 10 và 20 là cặp số bạn bè vì có chung tập ước nguyên tố là \(\{ 2,\ 5\}\); 10 và 8 không là cặp số bạn bè vì tập ước nguyên tố của 10 là {2, 5}, tập ước nguyên tố của 8 là {2}.

Yêu cầu: Cho trước hai số nguyên dương \(p\ và\ q\ (p < q)\), hãy đếm số lượng cặp số bạn bè \((x,\ y)\) thỏa mãn\(\ p \leq \ x < y \leq q.\)

Dữ liệu:

+ Gồm một dòng duy nhất ghi hai số nguyên dương \(p\ \)và \(q\) \(\left( p < q \leq 10^{6} \right).\)

Kết quả:

+ Ghi một số nguyên là kết quả bài toán.

Ví dụ:

Ràng buộc:

+ Có \(60\%\) số test có \(p < q \leq 260;\)

+ Có \(40\%\) số test có \(260 < p < q \leq 10^{6}.\)