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>
from math import *
# from sys import stdin,stdout

def binarySearch(arr,x,i):
	l=i
	r=len(arr)-1 
	while l <= r: 
		mid = (l + r)//2; 
		if arr[mid] == x: 
			return mid 
		elif arr[mid] < x: 
			l = mid + 1
		else: 
			r = mid - 1
	return -1

def js(arr,x):
	l=0
	r=len(arr)-1
	ans=-1
	while(l<=r):
		m=(l+r)//2
		if(arr[m]<=x):
			ans=m
			l=m+1
		else:
			r=m-1
	return ans

def jg(arr,x):
	l=0
	r=len(arr)-1
	ans=-1
	while(l<=r):
		m=(l+r)//2
		if(arr[m]>=x):
			ans=m
			r=m-1
		else:
			l=m+1
	return ans

# def ceil(a,b):
# 	if a%b == 0:
# 		return int(a/b)
# 	else:
# 		return (a//b + 1)

# from collections import deque

# n,m,k=map(int,input().split())
# ar=list(map(int,input().split()))

# q=[]
# sm=[0]*(m+1)
# for i in range(m+1):
# 	queue = deque()
# 	q.append(queue)


# ans=1
# for i in range(m+1)
# 	q[ar[i]].append(i)
# 	if(len(sm[ar[i]])==0):
# 		sm[ar[i]].append(1)
# 	else:

# 	while q[ar[i]]:

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
p1=[]
for i in range(n):
	if(i==0):
		if(a[i]==0):
			p1.append(0)
		else:
			p1.append(1)
	else:
		if(a[i]==0):
			p1.append(0)
		else:
			if(a[i-1]==0):
				p1.append(1)
			else:
				p1.append(1+p1[i-1])

p2=[]
for i in range(m):
	if(i==0):
		if(b[i]==0):
			p2.append(0)
		else:
			p2.append(1)
	else:
		if(b[i]==0):
			p2.append(0)
		else:
			if(b[i-1]==0):
				p2.append(1)
			else:
				p2.append(1+p2[i-1])
# p2[2]+=1
# print(p1,p2)

f=[]
for i in range(1,int(k**0.5)+1):
	if(k%i==0):
		if(k%(k//i)==0 and k//i!=i):
			f.append(k//i)
		f.append(i)
f.sort()
# print(f)
ans=0
for i in range(len(f)):
	a1=0
	for j in range(len(p2)):
		if(j<m-1):
			if(p2[j+1]==0 and p2[j]>=k//f[i]):
				a1+=p2[j]-k//f[i] + 1
		else:
			if(p2[j]>=k//f[i]):
				a1+=p2[j]-k//f[i] + 1

	a2=0
	for j in range(len(p1)):
		if(j<n-1):
			if(p1[j+1]==0 and p1[j]>=f[i]):
				a2+=p1[j]-f[i] + 1
		else:
			if(p1[j]>=f[i]):
				a2+=p1[j]-f[i] + 1
	ans+=a1*a2
print(ans)