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 main;

import java.awt.Point;
import java.io.*;
import java.util.*;

public final class Main {
    BufferedReader br;
    StringTokenizer stk;

    public static void main(String[] args) throws Exception {
        new Main().run();
    }
    
    {
        stk = null;
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    
    long mod = 1000_000_000 + 7;
    
    void run() throws Exception {
        int n = ni(), m = ni(), k = ni();
        int[] a = new int[n];
        int[] b = new int[m];
        for(int i = 0; i < n; i++)
            a[i] = ni();
        for(int i = 0; i < m; i++)
            b[i] = ni();
        
        List<Integer> divs = pairs(k);
        //System.out.println(divs);
        
        for(int i = 1; i < n; i++)
            a[i] += a[i - 1];
        for(int i = 1; i < m; i++)
            b[i] += b[i - 1];
        
        long total = 0;
        for(int num : divs) {
            int A = num;
            int B = k / num;
            total += count(A, a) * count(B, b);
            if(A != B)
                total += count(B, a) * count(A, b);
        }
        System.out.println(total);
    }
    
    int count(int size, int[] a) {
        int fptr = 0, bptr = size - 1;
        int count = 0;
        while(bptr < a.length) {
            long get = get(fptr, bptr, a);
            if(get == size)
                count++;
            fptr++; bptr++;
        }
        return count;
    }
    
    List<Integer> pairs(int k) {
        List<Integer> list = new ArrayList<>();
        for(int i = 1; i*i <= k; i++) {
            if(k % i == 0)
                list.add(i);
        }
        return list;
    }
    
    //Reader & Writer
    String nextToken() throws Exception {
        if (stk == null || !stk.hasMoreTokens()) {
            stk = new StringTokenizer(br.readLine(), " ");
        }
        return stk.nextToken();
    }

    String nt() throws Exception {
        return nextToken();
    }

    int ni() throws Exception {
        return Integer.parseInt(nextToken());
    }

    long nl() throws Exception {
        return Long.parseLong(nextToken());
    }
    
    double nd() throws Exception {
        return Double.parseDouble(nextToken());
    }
    
    //Some Misc methods
    long get(int l, int r, int[] a) {
        return l == 0 ? a[r] : a[r] - a[l - 1];
    }
    
    void shuffle(long[] a) {
        Random r = new Random();
        for(int i = 0; i < a.length; i++) {
            int idx = r.nextInt(a.length);
            long temp = a[i];
            a[i] = a[idx];
            a[idx] = temp;
        }
    }
}