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.*;
import java.lang.*;
import java.lang.reflect.Array;
import java.math.*;
import java.util.stream.Collectors;
public class JavaApplication1 {
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {

 
 BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
     String in[] = bf.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
         int m = Integer.parseInt(in[1]);
          int k = Integer.parseInt(in[2]);
          long temp=0l;
           long temp1=0l;

           String in1[] = bf.readLine().split(" ");
            a=new boolean[n];
           for(int i=0;i<n;i++){int x=Integer.parseInt(in1[i]);
           if(x==1){a[i]=true;temp++;}
           }
          
            String in2[] = bf.readLine().split(" ");
             a1=new boolean[m];
           for(int i=0;i<m;i++){int x=Integer.parseInt(in2[i]);
           if(x==1){a1[i]=true;temp1++;}}
          
  
   
       PriorityQueue<Integer> min=new PriorityQueue();
       PriorityQueue<Integer> max=new PriorityQueue<>((x, y) -> y - x);
 int sum=0;
 max.add(k);
 min.add(1);
 for(int i=2;i*i<=k;i++){
 if(k%i==0){sum++;min.add(i);max.add(k/i);}
 }
 
 int r=sum+min.size();
 int l=0;
 long count=0l;
 if(k==1){
      System.out.println(temp*temp1);
 }
 else if((temp*temp1)==0){System.out.println("0");}
 else {
 while(l<=r){
     
    
  
count+=counter(min.poll(), max.poll(), n,m);
  
 
    
 r--;
     l++;
 }
         System.out.println(count);
    }
    
  
    }
    static   boolean  a[];
   static   boolean  a1[];
    public static long counter (int l,int r,int n,int m) {
     long count=0;
       
      if(l<=n&&r<=m) {
          int count1=0;
          int inc=0;
    for(int ii=0;ii<m;ii++){
       
           if(a1[ii]){inc++;if(inc==r){inc--;count1++;}}
           else{inc=0;}
           }
    inc=0;
     long count2=0;
      for(int k=0;k<n;k++){
      if(a[k]){inc++;if(inc==l){inc--;count2++;}}
           else{inc=0;}
            
     }
      count+=(count1*count2);
      }
      
      
      
    
       if(l!=r&&l<=m&&r<=n){
           int count1=0;
          int inc=0;
    for(int ii=0;ii<m;ii++){
       
           if(a1[ii]){inc++;if(inc==l){inc--;count1++;}}
           else{inc=0;}
           }
    inc=0;
     long count2=0;
      for(int k=0;k<n;k++){
      if(a[k]){inc++;if(inc==r){inc--;count2++;}}
           else{inc=0;}
            
     }
      count+=(count1*count2);
       
       }
     return count;
    }
    
   
   
 
}