Bạn được cho 1 dãy ~A~ gồm ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ và dãy ~B~ gồm ~m~ số nguyên dương ~B_1, B_2, ... B_m~ và một số ~k~

Một cặp số ~(i,j)~ được gọi là tốt nếu như ~A_i~ ~\vdots~ ~(~ ~B_j \times k~ ~)~ với ~\vdots~ là kí hiệu chia hết

Hãy tìm số lượng của các cặp tốt

Input

Dòng đầu là số nguyên dương ~n~, ~m~ và ~k~ ~(1 \le n,m \le 10^5 , 1 \le k \le 10^3)~.

Dòng tiếp theo là ~n~ số nguyên dương ~A_i~ ~(1 \le A_i \le 10^6 )~

Dòng tiếp theo là ~m~ số nguyên dương ~B_i~ ~(1\le B_i \le 10^6)~

Output

Một dòng duy nhất là số lượng các cặp tốt

Sample Input

3 3 1
1 3 4 
1 3 4

Sample Output

5