Bài 3 : Hợp chất hóa học (5.0 điểm)

Trong phòng thí nghiệm hóa học, Giáo sư X đang nghiên cứu phản ứng giữa hai nhóm chất xúc tác. Nhóm A gồm \(N\) lọ hóa chất, lọ thứ \(i\) có nồng độ \(A_i\). Nhóm B gồm \(M\) lọ hóa chất, lọ thứ \(j\) có nồng độ \(B_j\).

Giáo sư phát hiện ra rằng, nếu trộn lọ thứ \(i\) của nhóm A và lọ thứ \(j\) của nhóm B, phản ứng sẽ tạo ra một hợp chất hoàn hảo khi và chỉ khi tích nồng độ của chúng đúng bằng một hằng số \(K\) (\(A_i \times B_j = K\)).

Hãy giúp giáo sư đếm xem có bao nhiêu cặp chỉ số \((i, j)\) (\(1 \le i \le N, 1 \le j \le M\)) có thể tạo ra hợp chất hoàn hảo này.

Input

Vào từ tệp văn bản HOPCHAT.INP có cấu trúc:

• Dòng đầu tiên chứa ba số nguyên \(N, M, K\) (\(1 \le N, M \le 2 \cdot 10^5, |K| \le 10^{18}\)).
• Dòng thứ hai chứa \(N\) số nguyên biểu diễn dãy \(A\) (\(|A_i| \le 10^9\)).
• Dòng thứ ba chứa \(M\) số nguyên biểu diễn dãy \(B\) (\(|B_j| \le 10^9\)).

Output

Ghi ra tệp văn bản HOPCHAT.OUT một số nguyên duy nhất là số cặp \((i, j)\) thỏa mãn.

Example

3 3 6
2 3 6
3 2 1

3

Scoring

• Subtask 1 (\(30\%\) số điểm): \(N, M \le 1000\).
• Subtask 2 (\(30\%\) số điểm): \(K = 0\).
• Subtask 3 (\(40\%\) số điểm): Không có ràng buộc gì thêm.