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>
function solv() {
    var ip = readline().split(' ').map(x => parseInt(x))

    var x = ip[0]
    var y = ip[1]
    var pp = ip[2]

    var s = readline().split(' ').map(x => parseInt(x))
    var z = readline().split(' ').map(x => parseInt(x))

    var precZ = {}
    var ct = 0
    for (n = 0; n < y; n++) {
        if (z[n]) ct++;
        else {
            if (precZ[ct] == null) precZ[ct] = 1;
            else precZ[ct] += 1;
            ct = 0;
        }
    }
    if (ct) {
        if (precZ[ct] == null) precZ[ct] = 1;
        else precZ[ct] += 1;
    }

    ct = 0
    var segsZ = JSON.parse(JSON.stringify(precZ))
    var propz = []
    for (var n in precZ) {
        propz.push([n * 1, precZ[n]])
    }
    propz.sort((a, b) => {
        return b[0] - a[0]
    })

    for (var n = 0; n < propz.length; n++) {
        for (var k = propz[n][0] - 1; k >= 1; k--) {
            segsZ[k] = segsZ[k] == null ? (propz[n][0] - k + 1) * propz[n][1] : segsZ[k] + (propz[n][0] - k + 1) * propz[n][1];
        }
    }

    var precS = {}
    ct = 0
    for (var n = 0; n < x; n++) {
        if (s[n]) ct++;
        else {
            if (precS[ct] == null) precS[ct] = 1;
            else precS[ct] += 1;
            ct = 0;
        }
    }
    if (ct) {
        if (precS[ct] == null) precS[ct] = 1;
        else precS[ct] += 1;
    }

    ct = 0
    var segsS = JSON.parse(JSON.stringify(precS))
    var props = []
    for (var n in precS) {
        props.push([n * 1, precS[n]])
    }
    props.sort((a, b) => {
        return b[0] - a[0]
    })

    for (var n = 0; n < props.length; n++) {
        for (var k = props[n][0] - 1; k >= 1; k--) {
            segsS[k] = segsS[k] == null ? (props[n][0] - k + 1) * props[n][1] : segsS[k] + (props[n][0] - k + 1) * props[n][1];
        }
    }


    var res = 0;

    for (var n = 1; n * n <= pp; n++) {
        if (pp % n == 0 && n * n != pp) {
            res += (segsS[n] == null ? 0 : segsS[n]) * (segsZ[pp / n] == null ? 0 : segsZ[pp / n])
            res += (segsZ[n] == null ? 0 : segsZ[n]) * (segsS[pp / n] == null ? 0 : segsS[pp / n])
        }
        else res += (segsS[n] == null ? 0 : segsS[n]) * (segsZ[pp / n] == null ? 0 : segsZ[pp / n])
    }

    print(res)
}

var tc = 1;
//tc = parseInt(readline());
while (tc--) solv()