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 collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect #bisect(list, num, beg, end)
import math
def turn(b):
    bdash = []
    m = len(b)
    j = 0
    while j < m:
        tmp = j
        while j + 1 < m and b[j+1] == b[tmp]:
            j += 1
        if b[tmp] == 1:
            bdash.append(j - tmp + 1)
        j += 1
    return bdash
def test_case():
    info = list(map(int, input().split()))
    n, m, k = info
    ksq = int(math.ceil(k**0.5))
    # n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ans = 0
    bdash = turn(b)
    adash = turn(a)
    bdash.sort(reverse=True)
    adash.sort(reverse=True)
    # print(bdash, adash)
    dp = {}
    for ydim in adash:
        if ydim in dp:
            ans += dp[ydim]
            continue
        now = 0
        for xdim in bdash:
            # got xdim X ydim area
            if (xdim, ydim) in dp:
                now += dp[(xdim, ydim)]
                continue
            nnow = 0
            for y in range(1, ydim + 1):
                x = k // y
                if x*y == k and x <= xdim and y <= ydim:
                    # print('x', xdim, 'y', y,  (xdim - (k // y) + 1) * max(1, ydim - y + 1))
                    nnow += (xdim - x + 1) * (ydim - y + 1)
            now += nnow
            dp[(xdim, ydim)] = nnow
        dp[ydim] = now
        # dp[(ydim, xdim)] = now
        ans += now
    return ans
ret = test_case()
if ret != None:
    print(ret)
