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>
def examA():
    t = I()
    ans = []
    for _ in range(t):
        N = I()
        A = LI()
        flag = False
        for i,a in enumerate(A):
            if a%2==0:
                flag = True
                ans.append((1,i+1))
                break
        if flag:
            continue
        if N==1:
            ans.append(-1)
            continue
        ans.append(2)
    for v in ans:
        if v==2:
            print(2)
            print("1 2")
        elif v==-1:
            print(-1)
        else:
            print(v[0])
            print(v[1])
    return

def examB():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        # divisors.sort()
        return divisors
    N, M, K = LI()
    a = LI()
    b = LI()
    A = defaultdict(int); B = defaultdict(int)
    cur = 0
    for i in range(N):
        if a[i]==1:
            cur += 1
        else:
            if cur>=1:
                A[cur] += 1
                cur = 0
    if cur>0:
        A[cur] += 1
    cur = 0
    for i in range(M):
        if b[i]==1:
            cur += 1
        else:
            if cur>=1:
                B[cur] += 1
                cur = 0
    if cur>0:
        B[cur] += 1

    SA = [0]*(N+2)
    SB = [0]*(M+2)

    for i in range(1,N+1)[::-1]:
        SA[i] = SA[i+1]+A[i]
    for i in range(1,M+1)[::-1]:
        SB[i] = SB[i+1]+B[i]

    #print(SA)
    #print(SB)

    SA2 = [0]*(N+2)
    SB2 = [0]*(M+2)

    for i in range(1, N + 1)[::-1]:
        SA2[i] = SA2[i+1] + SA[i+1] + A[i]
    for i in range(1, M + 1)[::-1]:
        SB2[i] = SB2[i+1] + SB[i+1] + B[i]

    #print(SA2)
    #print(SB2)

    S = make_divisors(K)
    if len(S)%2==1:
        S.append(S[-1])
    loop = len(S)//2

    ans = 0
    for i in range(loop):
        x = S[i*2]; y = S[i*2+1]
        if x<=N and y<=M:
            ans += SA2[x]*SB2[y]
        #print(ans,x,y)
        if x==y:
            continue
        x = S[i*2+1]; y = S[i*2]
        if x <= N and y <= M:
            ans += SA2[x]*SB2[y]
        #print(ans,x,y)
    print(ans)
    return

def examC():
    N = I()
    S = SI()

    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]



if __name__ == '__main__':
    examB()

"""

"""