You are given an array a of length n and array b of length m both consisting of only integers 0 and 1. Consider a matrix c of size n × m formed by following rule: c_{i, j} = a_i ⋅ b_j (i.e. a_i multiplied by b_j). It's easy to see that c consists of only zeroes and ones too.

How many subrectangles of size (area) k consisting only of ones are there in c?

A subrectangle is an intersection of a consecutive (subsequent) segment of rows and a consecutive (subsequent) segment of columns. I.e. consider four integers x_1, x_2, y_1, y_2 (1 ≤ x_1 ≤ x_2 ≤ n, 1 ≤ y_1 ≤ y_2 ≤ m) a subrectangle c[x_1 ... x_2][y_1 ... y_2] is an intersection of the rows x_1, x_1+1, x_1+2, ..., x_2 and the columns y_1, y_1+1, y_1+2, ..., y_2.

The size (area) of a subrectangle is the total number of cells in it.

Input

The first line contains three integers n, m and k (1 ≤ n, m ≤ 40 000, 1 ≤ k ≤ n ⋅ m), length of array a, length of array b and required size of subrectangles.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 1), elements of a.

The third line contains m integers b_1, b_2, …, b_m (0 ≤ b_i ≤ 1), elements of b.

Output

Output single integer — the number of subrectangles of c with size (area) k consisting only of ones.

Examples

Input


3 3 2
1 0 1
1 1 1


Output


4


Input


3 5 4
1 1 1
1 1 1 1 1


Output


14

Note

In first example matrix c is:

<image>

There are 4 subrectangles of size 2 consisting of only ones in it:

<image>

In second example matrix c is:

<image>
t = input().split(" ")
a = input().split(" ")
b = input().split(" ")
c = []
m = []
for j in range(1, int(int(t[2])**(1/2)) + 1):
    if int(t[2]) % j == 0:
        m.append(j)
        if j != int(int(t[2])/j):
            m.append(int(int(t[2])/j))

for i in range(0, len(a)):
    a[i] = int(a[i])
for i in range(0, len(b)):
    b[i] = int(b[i])
a0 = []
b0 = []

for p in range(0, len(a)):
    if a[p] == 0:
        a0.append(p)
for s in range(0, len(b)):
    if b[s] == 0:
        b0.append(s)

filas = []
columnas = []
if len(b0) != 0:
    columnas = [b0[0], len(b) - b0[len(b0)-1]-1]
else:
    columnas = [len(b)]

if len(a0) != 0:
    filas = [a0[0], len(a) - a0[len(a0)-1]-1]
else:
    filas = [len(a)]

for i in range(1, len(b0)):
    columnas.append(b0[i] - b0[i-1]-1)

for i in range(1, len(a0)):
    filas.append(a0[i] - a0[i-1]-1)

tot = 0
filas.sort()
columnas.sort()
filasn = []
val = []
colm = []
valc = []
for i in filas:
    if i not in filasn:
        filasn.append(i)
        val.append(0)
for i in columnas:
    if i not in colm:
        colm.append(i)
        valc.append(0)

v = len(filasn)-1
while filasn[v] * colm[len(colm)-1] >= int(t[2]) and v > 0:
    v -= 1
z = len(colm)-1
while colm[z] * filasn[len(filasn)-1] >= int(t[2]) and z > 0:
    z -= 1

for i in range(0, len(filasn)):
    for j in range(0, len(filas)):
        if filasn[i] == filas[j]:
            val[i] += 1
for i in range(0, len(colm)):
    for j in range(0, len(columnas)):
        if colm[i] == columnas[j]:
            valc[i] += 1

for i in range(0, len(m)):
    for j in range(v, len(filasn)):
        for k in range(z, len(colm)):
            if m[i] <= filasn[j] and int(int(t[2])/m[i]) <= colm[k]:
                tot += (filasn[j]-m[i]+1) * (colm[k] - (int(t[2])/m[i])+1) * val[j] * valc[k]


print(int(tot))