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>
"""
    Template written to be used by Python Programmers.
    Use at your own risk!!!!
    Owned by enraged(rating - 5 star at CodeChef and Specialist at Codeforces).
"""
import sys
import heapq
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
# sys.setrecursionlimit(2*pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var): sys.stdout.write(str(var))
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [[val for i in range(n)] for j in range(m)]


def factor_pair(n):
    fact = set()
    i = 1
    while i <= sqrt(n):
        if n % i == 0:
            fact.add((i, n//i))
            fact.add((n//i, i))
        i += 1
    return fact


def solve(arr, number):
    ans, cnt = 0, 0
    for i in arr:
        if i == 1:
            cnt += 1
            if cnt >= number:
                ans += 1
        else:
            cnt = 0
    return ans


n, m, k = sp()
factor = factor_pair(k)
a = l()
b = l()
answer = 0
for i in factor:
    answer += solve(a, i[0])*solve(b, i[1])
out(answer)
