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>
import java.io.*;
import java.util.*;
import java.math.*;

public class p1323B {

	public void realMain() throws Exception {

		BufferedReader fin = new BufferedReader(new InputStreamReader(System.in), 1000000);

		String in = fin.readLine();

		String[] ar = in.split(" ");

		int n = Integer.parseInt(ar[0]);
		int m = Integer.parseInt(ar[1]);
		int k = Integer.parseInt(ar[2]);

		int[] a = new int[n];
		int[] b = new int[m];

		for(int i = 0; i < n; i++) {
			int ret = 0;
			boolean dig = false;
			for (int ch = 0; (ch = fin.read()) != -1; ) {
        			if (ch >= '0' && ch <= '9') {
            				dig = true;
           				ret = ret * 10 + ch - '0';
        			} else if (dig) break;
    			}

			a[i] = ret;
			
		}

		for(int i = 0; i < m; i++) {
			int ret = 0;
			boolean dig = false;
			for (int ch = 0; (ch = fin.read()) != -1; ) {
        			if (ch >= '0' && ch <= '9') {
            				dig = true;
           				ret = ret * 10 + ch - '0';
        			} else if (dig) break;
    			}

			b[i] = ret;
			
		}

		int[] cnta = new int[n];
		int[] cntb = new int[m];

		if(a[n - 1] == 1) {
			cnta[n - 1] = 1;
		}

		for(int i = n - 2; i >= 0; i--) {
			if(a[i] == 0) {
				cnta[i] = 0;
			} else {
				cnta[i] = 1 + cnta[i + 1];
			}
		}

		if(b[m - 1] == 1) {
			cntb[m - 1] = 1;
		}

		for(int i = m - 2; i >= 0; i--) {
			if(b[i] == 0) {
				cntb[i] = 0;
			} else {
				cntb[i] = 1 + cntb[i + 1];
			}
		}

		long ans = 0;

		for(int i = 1; i * i <= k; i++) {
			if( k % i != 0) {
				continue;
			}

			int other = k / i;

			int numhoriz1 = 0;
			int numvert1 = 0;
			int numhoriz2 = 0;
			int numvert2 = 0;

			for(int j = 0; j < n; j++) {
				if(cnta[j] >= i) {
					numhoriz1++;
				}
				if(cnta[j] >= other) {
					numhoriz2++;
				}
			}
			
			for(int j = 0; j < m; j++) {
				if(cntb[j] >= other) {
					numvert1++;
				}
				if(cntb[j] >= i) {
					numvert2++;
				}
			}

			if(i == other) {
				ans += numhoriz1 * numvert1;
			} else {
				//System.out.println(i + ": " + ans);
				ans += numhoriz1 * numvert1;
				ans += numhoriz2 * numvert2;
				//System.out.println(other + ": " + ans);
			}
		}

		System.out.println(ans);
			


	}


	public static void main(String[] args) throws Exception {
		p1323B a = new p1323B();
		a.realMain();
	}
}