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.
#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> operator+(const pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return pair<long long, long long>(a.first + b.first, a.second + b.second);
}
pair<long long, long long> operator-(const pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return pair<long long, long long>(a.first - b.first, a.second - b.second);
}
constexpr long double m_pi = 3.1415926535897932L;
constexpr long long MOD = 1000000007;
constexpr long long INF = 1LL << 61;
constexpr long double EPS = 1e-10;
template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
using vector3 = vector<vector2<T>>;
string operator*(const string& s, int k) {
  if (k == 0) return "";
  string p = (s + s) * (k / 2);
  if (k % 2 == 1) p += s;
  return p;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
struct Edge {
  int to, rev;
  long long cap;
  Edge(int _to, long long _cap, int _rev) {
    to = _to;
    cap = _cap;
    rev = _rev;
  }
};
void add_edge(vector<vector<Edge>>& G, int from, int to, long long cap,
              bool revFlag, long long revCap) {
  G[from].push_back(Edge(to, cap, (long long)G[to].size() + (from == to)));
  if (revFlag)
    G[to].push_back(Edge(from, revCap, (long long)G[from].size() - 1));
}
long long max_flow_dfs(vector<vector<Edge>>& G, long long v, long long t,
                       long long f, vector<bool>& used) {
  if (v == t) return f;
  used[v] = true;
  for (int i = 0; i < G[v].size(); ++i) {
    Edge& e = G[v][i];
    if (!used[e.to] && e.cap > 0) {
      long long d = max_flow_dfs(G, e.to, t, min(f, e.cap), used);
      if (d > 0) {
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}
long long max_flow(vector<vector<Edge>>& G, long long s, long long t) {
  long long flow = 0;
  for (;;) {
    vector<bool> used(G.size());
    for (long long(i) = (long long)(0); i < (long long)(used.size()); i++)
      used[i] = false;
    long long f = max_flow_dfs(G, s, t, INF, used);
    if (f == 0) {
      return flow;
    }
    flow += f;
  }
}
void BellmanFord(vector<vector<Edge>>& G, long long s, vector<long long>& d,
                 vector<long long>& negative) {
  d.resize(G.size());
  negative.resize(G.size());
  for (long long(i) = (long long)(0); i < (long long)(d.size()); i++)
    d[i] = INF;
  for (long long(i) = (long long)(0); i < (long long)(d.size()); i++)
    negative[i] = false;
  d[s] = 0;
  for (long long(k) = (long long)(0); k < (long long)(G.size() - 1); k++) {
    for (long long(i) = (long long)(0); i < (long long)(G.size()); i++) {
      for (long long(j) = (long long)(0); j < (long long)(G[i].size()); j++) {
        if (d[i] != INF && d[G[i][j].to] > d[i] + G[i][j].cap) {
          d[G[i][j].to] = d[i] + G[i][j].cap;
        }
      }
    }
  }
  for (long long(k) = (long long)(0); k < (long long)(G.size() - 1); k++) {
    for (long long(i) = (long long)(0); i < (long long)(G.size()); i++) {
      for (long long(j) = (long long)(0); j < (long long)(G[i].size()); j++) {
        if (d[i] != INF && d[G[i][j].to] > d[i] + G[i][j].cap) {
          d[G[i][j].to] = d[i] + G[i][j].cap;
          negative[G[i][j].to] = true;
        }
        if (negative[i] == true) negative[G[i][j].to] = true;
      }
    }
  }
}
vector<long long> Dijkstra(vector<vector<Edge>>& g, long long s) {
  vector<long long> ret(g.size(), INF);
  ret[s] = 0;
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      q;
  q.push({ret[s], s});
  while (!q.empty()) {
    auto [d, v] = q.top();
    q.pop();
    if (ret[v] < d) continue;
    for (auto e : g[v]) {
      if (chmin(ret[e.to], ret[v] + e.cap)) q.push({ret[e.to], e.to});
    }
  }
  return ret;
}
vector<vector<long long>> WarshallFloyd(vector<vector<Edge>>& g) {
  vector<vector<long long>> ret(g.size(), vector<long long>(g.size(), INF));
  for (long long(i) = (long long)(0); i < (long long)(ret.size()); i++)
    ret[i][i] = 0;
  for (long long(i) = (long long)(0); i < (long long)(g.size()); i++) {
    for (auto e : g[i]) chmin(ret[i][e.to], e.cap);
  }
  for (long long(i) = (long long)(0); i < (long long)(g.size()); i++) {
    for (long long(j) = (long long)(0); j < (long long)(g.size()); j++) {
      for (long long(k) = (long long)(0); k < (long long)(g.size()); k++) {
        if (ret[j][i] != INF && ret[i][k] != INF)
          chmin(ret[j][k], ret[j][i] + ret[i][k]);
      }
    }
  }
  return ret;
}
bool tsort(vector<vector<Edge>>& graph, vector<int>& order) {
  int n = graph.size(), k = 0;
  vector<int> in(n);
  for (auto& es : graph)
    for (auto& e : es) in[e.to]++;
  priority_queue<int, vector<int>, greater<int>> que;
  for (long long(i) = (long long)(0); i < (long long)(n); i++)
    if (in[i] == 0) que.push(i);
  while (que.size()) {
    int v = que.top();
    que.pop();
    order.push_back(v);
    for (auto& e : graph[v])
      if (--in[e.to] == 0) que.push(e.to);
  }
  if (order.size() != n)
    return false;
  else
    return true;
}
class Lca {
 public:
  const int n = 0;
  const int log2_n = 0;
  std::vector<std::vector<int>> parent;
  std::vector<int> depth;
  Lca() {}
  Lca(const vector<vector<Edge>>& g, int root)
      : n(g.size()),
        log2_n(log2(n) + 1),
        parent(log2_n, std::vector<int>(n)),
        depth(n) {
    dfs(g, root, -1, 0);
    for (int k = 0; k + 1 < log2_n; k++) {
      for (int v = 0; v < (int)g.size(); v++) {
        if (parent[k][v] < 0)
          parent[k + 1][v] = -1;
        else
          parent[k + 1][v] = parent[k][parent[k][v]];
      }
    }
  }
  void dfs(const vector<vector<Edge>>& g, int v, int p, int d) {
    parent[0][v] = p;
    depth[v] = d;
    for (auto& e : g[v]) {
      if (e.to != p) dfs(g, e.to, v, d + 1);
    }
  }
  int get(int u, int v) {
    if (depth[u] > depth[v]) std::swap(u, v);
    for (int k = 0; k < log2_n; k++) {
      if ((depth[v] - depth[u]) >> k & 1) {
        v = parent[k][v];
      }
    }
    if (u == v) return u;
    for (int k = log2_n - 1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
};
class UnionFind {
  vector<int> data;
  int n;

 public:
  UnionFind(int size) : data(size, -1), n(size) {}
  bool merge(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    n -= (x != y);
    return x != y;
  }
  bool same(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
  int num() { return n; }
};
template <typename T, typename F>
class SegmentTree {
 private:
  T identity;
  F merge;
  long long n;
  vector<T> dat;

 public:
  SegmentTree(F f, T id, vector<T> v) : merge(f), identity(id) {
    int _n = v.size();
    n = 1;
    while (n < _n) n *= 2;
    dat.resize(2 * n - 1, identity);
    for (long long(i) = (long long)(0); i < (long long)(_n); i++)
      dat[n + i - 1] = v[i];
    for (int i = n - 2; i >= 0; i--)
      dat[i] = merge(dat[i * 2 + 1], dat[i * 2 + 2]);
  }
  SegmentTree(F f, T id, int _n) : merge(f), identity(id) {
    n = 1;
    while (n < _n) n *= 2;
    dat.resize(2 * n - 1, identity);
  }
  void set_val(int i, T x) {
    i += n - 1;
    dat[i] = x;
    while (i > 0) {
      i = (i - 1) / 2;
      dat[i] = merge(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
  }
  T query(int l, int r) {
    T left = identity, right = identity;
    l += n - 1;
    r += n - 1;
    while (l < r) {
      if ((l & 1) == 0) left = merge(left, dat[l]);
      if ((r & 1) == 0) right = merge(dat[r - 1], right);
      l = l / 2;
      r = (r - 1) / 2;
    }
    return merge(left, right);
  }
};
template <typename T>
class FenwickTree {
  vector<T> data;
  int n;
  int p;

 public:
  FenwickTree(int n) : n(n) {
    data.resize(n + 1LL, 0);
    p = 1;
    while (p < data.size()) p *= 2;
  }
  T sum(int k) {
    T ret = 0;
    for (; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }
  T sum(int a, int b) { return sum(b) - sum(a); }
  void add(int k, T x) {
    for (++k; k <= n; k += k & -k) data[k] += x;
  }
  int lower_bound(long long w) {
    if (w <= 0) return -1;
    int x = 0;
    for (int k = p / 2; k > 0; k /= 2) {
      if (x + k <= n && data[x + k] < w) w -= data[x + k], x += k;
    }
    return x;
  }
};
template <typename T>
vector<T> divisor(T n) {
  vector<T> ret;
  for (T i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());
  return ret;
}
template <typename T>
vector<pair<T, int>> prime_factorization(T n) {
  vector<pair<T, int>> ret;
  for (T i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back({i, 0});
      while (n % i == 0) {
        n /= i;
        ret[ret.size() - 1].second++;
      }
    }
  }
  if (n != 1) ret.push_back({n, 1});
  return ret;
}
inline long long mod_pow(long long x, long long n, long long mod) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}
inline long long mod_inv(long long x, long long mod) {
  return mod_pow(x, mod - 2, mod);
}
class Combination {
 public:
  vector<long long> fact;
  vector<long long> fact_inv;
  long long mod;
  long long nCr(long long n, long long r) {
    if (n < r) return 0;
    if (n < mod) return ((fact[n] * fact_inv[r] % mod) * fact_inv[n - r]) % mod;
    long long ret = 1;
    while (n || r) {
      long long _n = n % mod, _r = r % mod;
      n /= mod;
      r /= mod;
      (ret *= nCr(_n, _r)) %= mod;
    }
    return ret;
  }
  long long nPr(long long n, long long r) {
    return (fact[n] * fact_inv[n - r]) % mod;
  }
  long long nHr(long long n, long long r) { return nCr(r + n - 1, r); }
  Combination(long long _n, long long _mod) {
    mod = _mod;
    long long n = min(_n + 1, mod);
    fact.resize(n);
    fact[0] = 1;
    for (long long(i) = (long long)(0); i < (long long)(n - 1); i++) {
      fact[i + 1] = (fact[i] * (i + 1LL)) % mod;
    }
    fact_inv.resize(n);
    fact_inv[n - 1] = mod_inv(fact[n - 1], mod);
    for (int i = n - 1; i > 0; i--) {
      fact_inv[i - 1] = fact_inv[i] * i % mod;
    }
  }
};
long long popcount(long long x) {
  x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
  x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
  x = (x & 0x0F0F0F0F0F0F0F0F) + (x >> 4 & 0x0F0F0F0F0F0F0F0F);
  x = (x & 0x00FF00FF00FF00FF) + (x >> 8 & 0x00FF00FF00FF00FF);
  x = (x & 0x0000FFFF0000FFFF) + (x >> 16 & 0x0000FFFF0000FFFF);
  x = (x & 0x00000000FFFFFFFF) + (x >> 32 & 0x00000000FFFFFFFF);
  return x;
}
constexpr long long mod = 998244353;
class UnionFindUndo {
 private:
  vector<int> data;
  stack<pair<int, int>> history;

 public:
  UnionFindUndo(int sz) { data.assign(sz, -1); }
  bool merge(int x, int y) {
    x = root(x), y = root(y);
    history.emplace(x, data[x]);
    history.emplace(y, data[y]);
    if (x == y) return (false);
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
  int root(int k) {
    if (data[k] < 0) return (k);
    return (root(data[k]));
  }
  int size(int k) { return (-data[root(k)]); }
  void undo() {
    data[history.top().first] = history.top().second;
    history.pop();
    data[history.top().first] = history.top().second;
    history.pop();
  }
  void snapshot() {
    while (history.size()) history.pop();
  }
  void rollback() {
    while (history.size()) undo();
  }
};
template <typename F>
struct OfflineDynamicConnectivity {
  using edge = pair<int, int>;
  UnionFindUndo uf;
  int V, Q, segsz;
  vector<vector<edge>> seg;
  int comp;
  vector<pair<pair<int, int>, edge>> pend;
  map<edge, int> cnt, appear;
  OfflineDynamicConnectivity(int V, int Q) : uf(V), V(V), Q(Q), comp(V) {
    segsz = 1;
    while (segsz < Q) segsz <<= 1;
    seg.resize(2 * segsz - 1);
  }
  void insert(int idx, int s, int t) {
    auto e = minmax(s, t);
    if (cnt[e]++ == 0) appear[e] = idx;
  }
  void erase(int idx, int s, int t) {
    auto e = minmax(s, t);
    if (--cnt[e] == 0) pend.emplace_back(make_pair(appear[e], idx), e);
  }
  void add(int a, int b, const edge& e, int k, int l, int r) {
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      seg[k].emplace_back(e);
      return;
    }
    add(a, b, e, 2 * k + 1, l, (l + r) >> 1);
    add(a, b, e, 2 * k + 2, (l + r) >> 1, r);
  }
  void add(int a, int b, const edge& e) { add(a, b, e, 0, 0, segsz); }
  void build() {
    for (auto& p : cnt) {
      if (p.second > 0)
        pend.emplace_back(make_pair(appear[p.first], Q), p.first);
    }
    for (auto& s : pend) {
      add(s.first.first, s.first.second, s.second);
    }
  }
  void run(F f, int k = 0) {
    int add = 0;
    for (auto& e : seg[k]) {
      add += uf.merge(e.first, e.second);
    }
    comp -= add;
    if (k < segsz - 1) {
      run(f, 2 * k + 1);
      run(f, 2 * k + 2);
    } else if (k - (segsz - 1) < Q) {
      int query_index = k - (segsz - 1);
      f(query_index, uf);
    }
    for (auto& e : seg[k]) {
      uf.undo();
    }
    comp += add;
  }
};
template <long long mod, long long root>
class NTT {
 private:
  template <typename T>
  inline void bit_reverse(vector<T>& a) {
    int n = a.size();
    int i = 0;
    for (int j = 1; j < n - 1; ++j) {
      for (int k = n >> 1; k > (i ^= k); k >>= 1)
        ;
      if (j < i) swap(a[i], a[j]);
    }
  }
  void _ntt(vector<long long>& a, int sign) {
    const int n = a.size();
    assert((n ^ (n & -n)) == 0);
    long long tmp = (mod - 1) * mod_pow((long long)n, mod - 2, mod) % mod;
    long long h = mod_pow(root, tmp, mod);
    if (sign == -1) h = mod_pow(h, mod - 2, mod);
    bit_reverse(a);
    for (long long m = 1; m < n; m <<= 1) {
      const long long m2 = 2 * m;
      long long _base = mod_pow((long long)h, (long long)(n / m2), mod);
      long long _w = 1;
      for (int x = 0; x < m; ++x) {
        for (long long s = x; s < n; s += m2) {
          long long u = a[s];
          long long d = (a[s + m] * _w) % mod;
          a[s] = (u + d) % mod;
          a[s + m] = (u - d + mod) % mod;
        }
        _w = (_w * _base) % mod;
      }
    }
  }
  void ntt(vector<long long>& input) { _ntt(input, 1); }
  void intt(vector<long long>& input) {
    _ntt(input, -1);
    const long long n_inv = mod_pow((long long)input.size(), mod - 2, mod);
    for (auto& x : input) x = (x * n_inv) % mod;
  }

 public:
  vector<long long> convolution(const vector<long long>& a,
                                const vector<long long>& b) {
    int result_size = a.size() + b.size() - 1;
    int n = 1;
    while (n < result_size) n <<= 1;
    vector<long long> _a = a, _b = b;
    _a.resize(n, 0);
    _b.resize(n, 0);
    ntt(_a);
    ntt(_b);
    for (int i = 0; i < n; ++i) _a[i] = (_a[i] * _b[i]) % mod;
    intt(_a);
    _a.resize(result_size);
    return _a;
  }
  vector<long long> convolution(const vector<long long>& a, long long m,
                                long long mx_sz) {
    int result_size = mx_sz;
    int n = 1;
    while (n < result_size) n <<= 1;
    vector<long long> _a = a;
    _a.resize(n, 0);
    ntt(_a);
    for (int i = 0; i < n; ++i) _a[i] = mod_pow(_a[i], m, mod);
    intt(_a);
    _a.resize(result_size);
    return _a;
  }
};
int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  long long n, m, k;
  cin >> n >> m >> k;
  string s, t;
  cin >> s >> t;
  map<char, long long> mp;
  mp['A'] = 0;
  mp['G'] = 1;
  mp['C'] = 2;
  mp['T'] = 3;
  vector<long long> a(n);
  for (long long(i) = (long long)(0); i < (long long)(n); i++) a[i] = mp[s[i]];
  vector<vector<long long>> d(4, vector<long long>(n));
  vector<long long> last(4, -INF);
  for (long long(i) = (long long)(0); i < (long long)(n); i++) {
    last[a[i]] = i;
    for (long long(j) = (long long)(0); j < (long long)(4); j++)
      d[j][i] = i - last[j];
  }
  for (long long(i) = (long long)(0); i < (long long)(4); i++) last[i] = INF;
  for (int i = n - 1; i >= 0; i--) {
    last[a[i]] = i;
    for (long long(j) = (long long)(0); j < (long long)(4); j++)
      chmin(d[j][i], last[j] - i);
  }
  NTT<mod, 3> ntt;
  for (long long(i) = (long long)(0); i < (long long)(4); i++)
    for (long long(j) = (long long)(0); j < (long long)(n); j++)
      d[i][j] = (d[i][j] > k ? 1 : 0);
  vector<long long> ban(n + m - 1, 0);
  for (long long(i) = (long long)(0); i < (long long)(4); i++) {
    vector<long long> tmp(m, 0);
    for (long long(j) = (long long)(0); j < (long long)(m); j++)
      if (mp[t[j]] == i) tmp[j] = 1;
    reverse((tmp).begin(), (tmp).end());
    auto c = ntt.convolution(d[i], tmp);
    for (long long(j) = (long long)(0); j < (long long)(c.size()); j++)
      if (c[j] > 0) ban[j] = 1;
  }
  long long ans = 0;
  for (long long(i) = (long long)(m - 1); i < (long long)(n); i++) {
    if (ban[i] == 0) ans++;
  }
  cout << ans << "\n";
  return 0;
}
