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.util.*;
import java.io.*;
public class EdB {
	static long num = 998244353;
	public static void main(String[] args) throws Exception{
		

		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
 		StringTokenizer st = new StringTokenizer(bf.readLine());
 		int n = Integer.parseInt(st.nextToken());
 		int m = Integer.parseInt(st.nextToken());
 		int k = Integer.parseInt(st.nextToken());
 		ArrayList<Long> factors = new ArrayList<Long>();
 		for(long j = 1;j*j<=k;j++){
 			if (k%j == 0){
 				if (k == j*j)
 					factors.add(j);
 				else{
 					factors.add(j);
 					factors.add(k/j);
 				}
 			}
 		}
 		ArrayList<Integer> rows = new ArrayList<Integer>();
 		ArrayList<Integer> cols = new ArrayList<Integer>();
 		StringTokenizer st1 = new StringTokenizer(bf.readLine());
 		int count = 0;
 		for(int j = 0;j<n;j++){
 			int number = Integer.parseInt(st1.nextToken());
 			if (number == 0 && count!= 0){
 				rows.add(count);
 				count =0 ;
 			}
 			else if (number != 0){
 				count++;
 			}
 				
 		}
 		if (count!= 0)
 			rows.add(count);
 		StringTokenizer st2 = new StringTokenizer(bf.readLine());
 		int count1 = 0;
 		for(int j = 0;j<m;j++){
 			int number = Integer.parseInt(st2.nextToken());
 			if (number == 0 && count1!= 0){
 				cols.add(count1);
 				count1 =0 ;
 			}
 			else if (number != 0){
 				count1++;
 			}
 				
 		}
 		long ans = 0;
 		if (count1!= 0)
 			cols.add(count1);
 		for(long j : factors){
 			int row = 0;
 			for(int ts : rows){
 				row+=Math.max(ts-j+1,  0);
 			}
 			int col = 0;
 			for(int ts : cols){
 				col+=Math.max(ts-k/j+1,  0);
 			}
 			ans+=(long)(col)*(long)(row);
 		}
 		
 		out.println(ans);
	 		
 		out.close();
 		
 		
 		
 	}
}
 	
 
//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is

 		
 		
 		
 		
	


