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>
//package codeforces;

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class B1323 {

    private static Map<Integer, Map<Integer, Long>> cache = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        String[] line = sc.readLine().split(" ");
        long k = Long.parseLong(line[2]);
        String w1 = sc.readLine(); // n
        String w2 = sc.readLine(); // m
        if (k > 1) {
            List<Integer> parts1 = split(w1);
            List<Integer> parts2 = split(w2);
            List<Long> divs = getDivs(k);
            long answ = 0;

            Map<Integer, Long> m0 = new HashMap<>();

            for (int a : parts1) {
                Long r = m0.get(a);
                if (r != null) {
                    answ += r;
                } else {
                    long a0 = answ;
                    for (int b : parts2) {
                        answ += calc(a, b, k, divs);
                    }
                    long a1 = answ;
                    m0.put(a, a1 - a0);
                }
            }
            System.out.println(answ);
        } else {
            int a = count(w1);
            int b = count(w2);
            System.out.println(a * b);
        }
    }

    private static int count(String w1) {
        int a = 0;
        for (int i = 0; i < w1.length(); i++) {
            if (w1.charAt(i) == '1') {
                a++;
            }
        }
        return a;
    }

    private static long calc(int a, int b, long k, List<Long> divs) {
        final int ab = a * b;
        if (ab < k) return 0;
        if (ab == k) return 1;

        if (k == 2 && a == 2 && b == 2) {
            return 4;
        }

        if (a == 1) {
            return b - k + 1;
        }
        if (b == 1) {
            return a - k + 1;
        }
        if (a > b) {
            return calc(b, a, k, divs);
        }
        final Long res = getCache(a, b);
        if (res != null) {
            return res;
        }
        long r = 0;
        for (int i = 0; i < divs.size(); i++) {
            long x = divs.get(i);
            long y = k / x;
            r += c2(a, b, x, y);
            if (x != y) {
                r += c2(a, b, y, x);
            }
        }
        putCache(a, b, r);
        return r;
    }

    private static void putCache(int a, int b, long r) {
        cache.computeIfAbsent(a, k -> new HashMap<>()).put(b, r);
    }

    private static Long getCache(int a, int b) {
        final Map<Integer, Long> x1 = cache.get(a);
        if (x1 != null) {
            return x1.get(b);
        } else {
            return null;
        }
    }

    private static long c2(int a, int b, long x, long y) {
        long d1 = a - x;
        long d2 = b - y;
        if (d1 < 0 || d2 < 0) {
            return 0;
        }
        return (d1 + 1) * (d2 + 1);
    }

    private static List<Long> getDivs(long k) {
        List<Long> divs = new ArrayList<>();
        divs.add(1L);
        for (long i = 2; i * i <= k; i++) {
            if (k % i == 0) {
                divs.add(i);
            }
        }

        return divs;
    }

    private static List<Integer> split(String w1) {
        int curr = 0;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < w1.length(); i++) {
            char ch = w1.charAt(i);
            if (ch == '1') {
                curr++;
            } else if (ch == '0') {
                if (curr > 0) {
                    list.add(curr);
                    curr = 0;
                }
            }
        }
        if (curr > 0) {
            list.add(curr);
        }

        return list;
    }
}
