Leonid works for a small and promising start-up that works on decoding the human genome. His duties include solving complex problems of finding certain patterns in long strings consisting of letters 'A', 'T', 'G' and 'C'.

Let's consider the following scenario. There is a fragment of a human DNA chain, recorded as a string S. To analyze the fragment, you need to find all occurrences of string T in a string S. However, the matter is complicated by the fact that the original chain fragment could contain minor mutations, which, however, complicate the task of finding a fragment. Leonid proposed the following approach to solve this problem.

Let's write down integer k ≥ 0 — the error threshold. We will say that string T occurs in string S on position i (1 ≤ i ≤ |S| - |T| + 1), if after putting string T along with this position, each character of string T corresponds to the some character of the same value in string S at the distance of at most k. More formally, for any j (1 ≤ j ≤ |T|) there must exist such p (1 ≤ p ≤ |S|), that |(i + j - 1) - p| ≤ k and S[p] = T[j].

For example, corresponding to the given definition, string "ACAT" occurs in string "AGCAATTCAT" in positions 2, 3 and 6.

<image>

Note that at k = 0 the given definition transforms to a simple definition of the occurrence of a string in a string.

Help Leonid by calculating in how many positions the given string T occurs in the given string S with the given error threshold.

Input

The first line contains three integers |S|, |T|, k (1 ≤ |T| ≤ |S| ≤ 200 000, 0 ≤ k ≤ 200 000) — the lengths of strings S and T and the error threshold.

The second line contains string S.

The third line contains string T.

Both strings consist only of uppercase letters 'A', 'T', 'G' and 'C'.

Output

Print a single number — the number of occurrences of T in S with the error threshold k by the given definition.

Examples

Input

10 4 1
AGCAATTCAT
ACAT


Output

3

Note

If you happen to know about the structure of the human genome a little more than the author of the problem, and you are not impressed with Leonid's original approach, do not take everything described above seriously.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Deque;
import java.util.function.Supplier;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.Collection;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.function.Consumer;
import java.io.Closeable;
import java.io.Writer;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DFuzzySearch solver = new DFuzzySearch();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DFuzzySearch {
        Debug debug = new Debug(false);

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int m = in.ri();
            int k = in.ri();
            char[] S = new char[n];
            in.rs(S);
            char[] T = new char[m];
            in.rs(T);
            int[] transform = new int[128];
            transform['A'] = 0;
            transform['T'] = 1;
            transform['G'] = 2;
            transform['C'] = 3;
            for (int i = 0; i < n; i++) {
                S[i] = (char) transform[S[i]];
            }
            for (int i = 0; i < m; i++) {
                T[i] = (char) transform[T[i]];
            }
            int[][] source = new int[4][n];
            int[] pattern = new int[m];
            for (int i = 0; i < m; i++) {
                pattern[i] = T[i];
            }
            SequenceUtils.deepFill(source, 4);
            for (int i = 0; i < 4; i++) {
                int prev = -k - 1;
                for (int j = 0; j < n; j++) {
                    if (S[j] == i) {
                        prev = j;
                    }
                    if (j - prev <= k) {
                        source[i][j] = i;
                    }
                }
                int next = n + k;
                for (int j = n - 1; j >= 0; j--) {
                    if (S[j] == i) {
                        next = j;
                    }
                    if (next - j <= k) {
                        source[i][j] = i;
                    }
                }
            }
            debug.debugMatrix("source", source);
            debug.debugArray("pattern", pattern);

            boolean[] match = new MultiMatch().fastMatch(pattern, source, false);
            int ans = 0;
            for (boolean x : match) {
                if (x) {
                    ans++;
                }
            }
            out.println(ans);
        }

    }

    static class PrimitiveBuffers {
        public static Buffer<int[]>[] intPow2Bufs = new Buffer[30];
        public static Buffer<double[]>[] doublePow2Bufs = new Buffer[30];

        static {
            for (int i = 0; i < 30; i++) {
                int finalI = i;
                intPow2Bufs[i] = new Buffer<>(() -> new int[1 << finalI], x -> Arrays.fill(x, 0));
                doublePow2Bufs[i] = new Buffer<>(() -> new double[1 << finalI], x -> Arrays.fill(x, 0));
            }
        }

        public static int[] allocIntPow2(int n) {
            return intPow2Bufs[Log2.ceilLog(n)].alloc();
        }

        public static void release(int[] data) {
            intPow2Bufs[Log2.ceilLog(data.length)].release(data);
        }

        public static double[] allocDoublePow2(int n) {
            return doublePow2Bufs[Log2.ceilLog(n)].alloc();
        }

        public static double[][] allocDoublePow2Array(int n, int arraySize) {
            double[][] ans = new double[arraySize][];
            for (int i = 0; i < arraySize; i++) {
                ans[i] = allocDoublePow2(n);
            }
            return ans;
        }

        public static void release(double[] data) {
            doublePow2Bufs[Log2.ceilLog(data.length)].release(data);
        }

        public static void release(double[]... data) {
            for (double[] x : data) {
                release(x);
            }
        }

        public static int[][] allocIntPow2Array(int n, int arraySize) {
            int[][] ans = new int[arraySize][];
            for (int i = 0; i < arraySize; i++) {
                ans[i] = allocIntPow2(n);
            }
            return ans;
        }

        public static void release(int[]... data) {
            for (int[] x : data) {
                release(x);
            }
        }

    }

    static class SequenceUtils {
        public static void swap(double[] data, int i, int j) {
            double tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

        public static void deepFill(Object array, int val) {
            if (!array.getClass().isArray()) {
                throw new IllegalArgumentException();
            }
            if (array instanceof int[]) {
                int[] intArray = (int[]) array;
                Arrays.fill(intArray, val);
            } else {
                Object[] objArray = (Object[]) array;
                for (Object obj : objArray) {
                    deepFill(obj, val);
                }
            }
        }

        public static void deepFill(Object array, double val) {
            if (!array.getClass().isArray()) {
                throw new IllegalArgumentException();
            }
            if (array instanceof double[]) {
                double[] doubleArray = (double[]) array;
                Arrays.fill(doubleArray, val);
            } else {
                Object[] objArray = (Object[]) array;
                for (Object obj : objArray) {
                    deepFill(obj, val);
                }
            }
        }

        public static void reverse(double[] data, int l, int r) {
            while (l < r) {
                swap(data, l, r);
                l++;
                r--;
            }
        }

    }

    static class FastFourierTransform {
        private static double[][] realLevels = new double[30][];
        private static double[][] imgLevels = new double[30][];

        private static void prepareLevel(int i) {
            if (realLevels[i] == null) {
                realLevels[i] = new double[1 << i];
                imgLevels[i] = new double[1 << i];
                for (int j = 0, s = 1 << i; j < s; j++) {
                    realLevels[i][j] = Math.cos(Math.PI / s * j);
                    imgLevels[i][j] = Math.sin(Math.PI / s * j);
                }
            }
        }

        public static double[][] dotMul(double[][] a, double[][] b) {
            int n = a[0].length;
            double[][] ans = PrimitiveBuffers.allocDoublePow2Array(n, 2);
            for (int i = 0; i < n; i++) {
                mul(a[0][i], a[1][i], b[0][i], b[1][i], ans, i);
            }
            return ans;
        }

        public static void fft(double[][] p, boolean inv) {
            int m = Log2.ceilLog(p[0].length);
            int n = 1 << m;
            int shift = 32 - Integer.numberOfTrailingZeros(n);
            for (int i = 1; i < n; i++) {
                int j = Integer.reverse(i << shift);
                if (i < j) {
                    SequenceUtils.swap(p[0], i, j);
                    SequenceUtils.swap(p[1], i, j);
                }
            }

            double[][] t = new double[2][1];
            for (int d = 0; d < m; d++) {
                int s = 1 << d;
                int s2 = s << 1;
                prepareLevel(d);
                for (int i = 0; i < n; i += s2) {
                    for (int j = 0; j < s; j++) {
                        int a = i + j;
                        int b = a + s;
                        mul(realLevels[d][j], imgLevels[d][j], p[0][b], p[1][b], t, 0);
                        sub(p[0][a], p[1][a], t[0][0], t[1][0], p, b);
                        add(p[0][a], p[1][a], t[0][0], t[1][0], p, a);
                    }
                }
            }

            if (inv) {
                for (int i = 0, j = 0; i <= j; i++, j = n - i) {
                    double a = p[0][j];
                    double b = p[1][j];
                    div(p[0][i], p[1][i], n, p, j);
                    if (i != j) {
                        div(a, b, n, p, i);
                    }
                }
            }
        }

        public static void add(double r1, double i1, double r2, double i2, double[][] r, int i) {
            r[0][i] = r1 + r2;
            r[1][i] = i1 + i2;
        }

        public static void sub(double r1, double i1, double r2, double i2, double[][] r, int i) {
            r[0][i] = r1 - r2;
            r[1][i] = i1 - i2;
        }

        public static void mul(double r1, double i1, double r2, double i2, double[][] r, int i) {
            r[0][i] = r1 * r2 - i1 * i2;
            r[1][i] = r1 * i2 + i1 * r2;
        }

        public static void div(double r1, double i1, double r2, double[][] r, int i) {
            r[0][i] = r1 / r2;
            r[1][i] = i1 / r2;
        }

    }

    static class MultiMatch {
        private int[][] sumOf(int[][] pattern, boolean matchAll) {
            int p = pattern.length;
            int n = pattern[0].length;
            int[][] A = PrimitiveBuffers.allocIntPow2Array(n, p * 2 + 1);
            int[] accumulate = PrimitiveBuffers.allocIntPow2(n);
            for (int i = 0; i < n; i++) {
                accumulate[i] = 1;
            }
            if (matchAll) {
                for (int[] pat : pattern) {
                    for (int i = 0; i < n; i++) {
                        if (pat[i] == 0) {
                            accumulate[i] = 0;
                        }
                    }
                }
            }
            sumOf(pattern, 0, A, 0, accumulate);
            PrimitiveBuffers.release(accumulate);
            return A;
        }

        private void sumOf(int[][] s, int pick, int[][] sum, int id, int[] accumulate) {
            int len = s[0].length;
            if (id >= s.length) {
                for (int i = 0; i < len; i++) {
                    sum[pick][i] += accumulate[i];
                }
                return;
            }
            sumOf(s, pick + 0, sum, id + 1, accumulate);
            int[] data = PrimitiveBuffers.allocIntPow2(len);
            for (int j = 0; j < len; j++) {
                data[j] = accumulate[j] * s[id][j] * 2;
            }
            sumOf(s, pick + 1, sum, id + 1, data);
            for (int j = 0; j < len; j++) {
                data[j] = accumulate[j] * s[id][j] * s[id][j];
            }
            sumOf(s, pick + 2, sum, id + 1, data);
            PrimitiveBuffers.release(data);
        }

        public boolean[] fastMatch(int[] pattern, int[][] source, boolean matchAll) {
            int n = pattern.length;
            int s = source.length;
            int m = source[0].length;
            int total = s * 2;
            int[] prodA = PrimitiveBuffers.allocIntPow2(n);
            Arrays.fill(prodA, 1);
            if (matchAll) {
                for (int i = 0; i < n; i++) {
                    prodA[i] = pattern[i];
                }
            }
            int[][] Bs = sumOf(source, matchAll);
            double[][] B = PrimitiveBuffers.allocDoublePow2Array(m + n - 1, 2);
            double[][] A = PrimitiveBuffers.allocDoublePow2Array(m + n - 1, 2);
            double[][] sum = PrimitiveBuffers.allocDoublePow2Array(m + n - 1, 2);
            for (int i = 0; i <= total; i++) {
                int j = total - i;
                SequenceUtils.deepFill(B, 0d);
                if (j % 2 == 0) {
                    for (int k = 0; k < m; k++) {
                        B[0][k] = Bs[j][k];
                    }
                } else {
                    for (int k = 0; k < m; k++) {
                        B[0][k] = -Bs[j][k];
                    }
                }
                SequenceUtils.deepFill(A, 0d);
                for (int k = 0; k < n; k++) {
                    A[0][k] = prodA[k];
                }
                SequenceUtils.reverse(B[0], 0, m - 1);
                FastFourierTransform.fft(B, false);
                FastFourierTransform.fft(A, false);
                double[][] dm = FastFourierTransform.dotMul(A, B);
                for (int t = 0; t < 2; t++) {
                    for (int k = 0; k < dm[t].length; k++) {
                        sum[t][k] += dm[t][k];
                    }
                }
                for (int k = 0; k < n; k++) {
                    prodA[k] *= pattern[k];
                }
                PrimitiveBuffers.release(dm);
            }
            boolean[] possible = new boolean[m];
            FastFourierTransform.fft(sum, true);
            SequenceUtils.reverse(sum[0], 0, m - 1);
            for (int i = 0; i + n <= m; i++) {
                possible[i] = -0.5 < sum[0][i] && sum[0][i] < 0.5;
            }
            PrimitiveBuffers.release(sum);
            PrimitiveBuffers.release(A);
            PrimitiveBuffers.release(prodA);
            PrimitiveBuffers.release(B);
            PrimitiveBuffers.release(Bs);
            return possible;
        }

    }

    static class Buffer<T> {
        private Deque<T> deque;
        private Supplier<T> supplier;
        private Consumer<T> cleaner;
        private int allocTime;
        private int releaseTime;

        public Buffer(Supplier<T> supplier) {
            this(supplier, (x) -> {
            });
        }

        public Buffer(Supplier<T> supplier, Consumer<T> cleaner) {
            this(supplier, cleaner, 0);
        }

        public Buffer(Supplier<T> supplier, Consumer<T> cleaner, int exp) {
            this.supplier = supplier;
            this.cleaner = cleaner;
            deque = new ArrayDeque<>(exp);
        }

        public T alloc() {
            allocTime++;
            return deque.isEmpty() ? supplier.get() : deque.removeFirst();
        }

        public void release(T e) {
            releaseTime++;
            cleaner.accept(e);
            deque.addLast(e);
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public int rs(char[] data, int offset) {
            return readString(data, offset);
        }

        public int rs(char[] data) {
            return rs(data, 0);
        }

        public int readString(char[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read();
            }

            return offset - originalOffset;
        }

    }

    static class Log2 {
        public static int ceilLog(int x) {
            if (x <= 0) {
                return 0;
            }
            return 32 - Integer.numberOfLeadingZeros(x - 1);
        }

    }

    static class Debug {
        private boolean offline;
        private PrintStream out = System.err;
        static int[] empty = new int[0];

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager() == null;
        }

        public Debug debugMatrix(String name, int[][] matrix) {
            if (offline) {
                StringBuilder content = new StringBuilder("\n");
                for (int[] row : matrix) {
                    for (int cell : row) {
                        content.append(cell).append(' ');
                    }
                    content.append(System.lineSeparator());
                }
                debug(name, content);
            }
            return this;
        }

        public Debug debugArray(String name, int[] matrix) {
            if (offline) {
                debug(name, Arrays.toString(matrix));
            }
            return this;
        }

        public Debug debug(String name, String x) {
            if (offline) {
                out.printf("%s=%s", name, x);
                out.println();
            }
            return this;
        }

        public Debug debug(String name, Object x) {
            return debug(name, x, empty);
        }

        public Debug debug(String name, Object x, int... indexes) {
            if (offline) {
                if (x == null || !x.getClass().isArray()) {
                    out.append(name);
                    for (int i : indexes) {
                        out.printf("[%d]", i);
                    }
                    out.append("=").append("" + x);
                    out.println();
                } else {
                    indexes = Arrays.copyOf(indexes, indexes.length + 1);
                    if (x instanceof byte[]) {
                        byte[] arr = (byte[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof short[]) {
                        short[] arr = (short[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof boolean[]) {
                        boolean[] arr = (boolean[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof char[]) {
                        char[] arr = (char[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof int[]) {
                        int[] arr = (int[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof float[]) {
                        float[] arr = (float[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof double[]) {
                        double[] arr = (double[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof long[]) {
                        long[] arr = (long[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else {
                        Object[] arr = (Object[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    }
                }
            }
            return this;
        }

    }
}

