Mỗi truy vấn cho hai đoạn nguyên [a,b],[c,d] và một số k. Hãy đếm các cặp có thứ tự (x,y) sao cho x thuộc đoạn thứ nhất, y thuộc đoạn thứ hai và gcd(x,y)=k.
Hai tọa độ có vai trò riêng. Nếu cả (x,y) và (y,x) đều thuộc miền của truy vấn thì chúng được tính thành hai cặp khác nhau.
Input
Dòng đầu chứa số nguyên T, là số truy vấn.
T dòng tiếp theo, mỗi dòng chứa năm số nguyên a,b,c,d,k.
Output
Với mỗi truy vấn, in trên một dòng số cặp hợp lệ.
Constraints
1≤T,k≤5⋅104.
1≤a≤b≤5⋅104.
1≤c≤d≤5⋅104.
Scoring
Subtask 1 (50% số điểm): T≤100 và mọi cận tọa độ không vượt 200.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
3
2 4 3 5 1
2 4 3 5 2
4 6 6 8 2
Output
6
1
2
Giải thích: Ba truy vấn lần lượt có 6,1,2 cặp. Chẳng hạn ở truy vấn thứ hai, cặp duy nhất là (2,4).
Lời giải tóm tắt
Ý tưởng: Xây hàm F(n,m,k) đếm các cặp 1≤x≤n,1≤y≤m có gcd k. Sau khi chia hai tọa độ cho k, công thức là Σ_t μ(t)⌊n/(kt)⌋⌊m/(kt)⌋. Tiền xử lý tổng tiền tố Möbius và gom các t liên tiếp có cùng hai thương. Dùng bao hàm-loại trừ bốn góc để chuyển từ hai prefix sang hai đoạn bất kỳ.
Chứng minh đúng: Sau phép chia k, điều kiện trở thành hai số nguyên tố cùng nhau; chỉ báo Möbius đếm đúng các cặp đó. Trong mỗi khối thương, hai số sàn không đổi nên thay tổng từng μ bằng hiệu prefix không đổi kết quả. Bao hàm-loại trừ lần lượt bỏ phần x<a và y<c rồi cộng lại giao bị bỏ hai lần, do đó trả đúng hình chữ nhật [a,b]×[c,d].
Độ phức tạp: Tiền xử lý O(V log log V); mỗi truy vấn dùng O(√V) cho mỗi prefix và O(V) bộ nhớ, với V=50000.