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 CFA {
  BufferedReader br;
  PrintWriter out;
  StringTokenizer st;
  boolean eof;
  private static final long MOD = 1000L * 1000L * 1000L + 7;
  private static final int[] dx = {0, -1, 0, 1};
  private static final int[] dy = {1, 0, -1, 0};
  private static final String yes = "Yes";
  private static final String no = "No";

  void solve() {
//    int T = nextInt();
    int T = 1;
    for (int i = 0; i < T; i++) {
      helper();
    }
  }

  void helper() {
    int n = nextInt();
    int m = nextInt();
    long k = nextLong();
    int[] a = nextIntArr(n);
    int[] b = nextIntArr(m);
    List<Integer> l1 = find(a);
    List<Integer> l2 = find(b);
    Collections.sort(l1);
    Collections.sort(l2);
    int[] p1 = prefCal(l1);
    int[] p2 = prefCal(l2);
    long res = 0;
    List<Pair> good = new ArrayList<>();
    for (long i = 1; i * i <= k; i++) {
      if (k % i == 0) {
        good.add(new Pair(i, k / i));
        if (i * i != k) {
          good.add(new Pair(k / i, i));
        }
      }
    }
    for (Pair p : good) {
      int first = -1;
      for (int i = 0; i < l1.size(); i++) {
        long d = l1.get(i) - p.x;
        if (d >= 0) {
          first = i;
          break;
        }
      }
      if (first == -1) {
        continue;
      }
      int second = -1;
      for (int i = 0; i < l2.size(); i++) {
        long d = l2.get(i) - p.y;
        if (d >= 0) {
          second = i;
          break;
        }
      }
      if (second == -1) {
        continue;
      }
      res += p1[first] * p2[second];
      res -= p1[first] * (l2.size() - 1 - second + 1) * (p.y - 1);
      res -= p2[second] * (l1.size() - 1 - first + 1) * (p.x - 1);
      res += (l2.size() - 1 - second + 1) * (l1.size() - 1 - first + 1) * (p.y - 1) * (p.x - 1);
    }
    outln(res);
  }

  class Pair {
    long x;
    long y;
    public Pair(long x, long y) {
      this.x = x;
      this.y = y;
    }

    @Override
    public String toString() {
      return x + " " + y;
    }
  }

  int[] prefCal(List<Integer> ls) {
    int sz = ls.size();
    int[] res = new int[sz + 1];
    for (int i = sz - 1; i >= 0; i--) {
      res[i] = res[i + 1] + ls.get(i);
    }
    return res;
  }

  List<Integer> find(int[] arr) {
    int n = arr.length;
    int start = 0;
    List<Integer> res = new ArrayList<>();
    while (start < n) {
      if (arr[start] == 0) {
        start++;
        continue;
      }
      int end = start;
      while (end < n && arr[end] == arr[start]) {
        end++;
      }
      res.add(end - start);
      start = end;
    }
    return res;
  }

  void shuffle(int[] a) {
    int n = a.length;
    for(int i = 0; i < n; i++) {
      int r = i + (int) (Math.random() * (n - i));
      int tmp = a[i];
      a[i] = a[r];
      a[r] = tmp;
    }
  }

  long gcd(long a, long b) {
    while(a != 0 && b != 0) {
      long c = b;
      b = a % b;
      a = c;
    }
    return a + b;
  }
  int gcd(int a, int b) {
    while(a != 0 && b != 0) {
      int c = b;
      b = a % b;
      a = c;
    }
    return a + b;
  }
  private void outln(Object o) {
    out.println(o);
  }
  private void out(Object o) {
    out.print(o);
  }
  private void formatPrint(double val) {
    outln(String.format("%.9f", val));
  }
  public CFA() {
    br = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out);
    solve();
    out.close();
  }
  public static void main(String[] args) {
    new CFA();
  }

  public long[] nextLongArr(int n) {
    long[] res = new long[n];
    for(int i = 0; i < n; i++)
      res[i] = nextLong();
    return res;
  }
  public int[] nextIntArr(int n) {
    int[] res = new int[n];
    for(int i = 0; i < n; i++)
      res[i] = nextInt();
    return res;
  }
  public String nextToken() {
    while (st == null || !st.hasMoreTokens()) {
      try {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e) {
        eof = true;
        return null;
      }
    }
    return st.nextToken();
  }
  public String nextString() {
    try {
      return br.readLine();
    } catch (IOException e) {
      eof = true;
      return null;
    }
  }
  public int nextInt() {
    return Integer.parseInt(nextToken());
  }
  public long nextLong() {
    return Long.parseLong(nextToken());
  }
  public double nextDouble() {
    return Double.parseDouble(nextToken());
  }
}