#include <bits/stdc++.h>
using namespace std;
template <class T>
T read() {
  T value;
  cin >> value;
  return value;
}
int read_int() { return read<int>(); }
size_t read_size() { return read<size_t>(); }
long long read_ll() { return read<long long>(); }
string read_string() { return read<string>(); }
template <class T>
void read_vector(vector<T> &a, size_t size) {
  a.resize(size);
  for (T &value : a) cin >> value;
}
void read_pairs(vector<pair<int, int> > &a, size_t size) {
  a.resize(size);
  for (pair<int, int> &value : a) cin >> value.first >> value.second;
}
void read_iii(vector<pair<pair<int, int>, int> > &a, size_t size) {
  a.resize(size);
  for (pair<pair<int, int>, int> &value : a)
    cin >> value.first.first >> value.first.second >> value.second;
}
const char SPACE = ' ', ENDL = '\n';
template <class T>
void print(vector<T> &a, char sep = SPACE) {
  for (T &value : a) cout << value << sep;
  cout << '\n';
}
template <class T>
vector<int> compress(vector<T> &values) {
  vector<T> sorted = values;
  sort(sorted.begin(), sorted.end());
  sorted.resize(unique(sorted.begin(), sorted.end()) - sorted.begin());
  vector<int> result(values.size());
  for (int i = 0; i < values.size(); ++i) {
    result[i] =
        lower_bound(sorted.begin(), sorted.end(), values[i]) - sorted.begin();
  }
  return result;
}
int get_bit(long long mask, int bit) { return (int)((mask >> bit) & 1); }
string reverse(string s) {
  reverse(s.begin(), s.end());
  return s;
}
vector<int> reverse(vector<int> a) {
  reverse(a.begin(), a.end());
  return a;
}
vector<int> concat_separated(vector<int> &a, vector<int> &b, int sep = -1) {
  size_t n = a.size(), m = b.size();
  vector<int> s(n + 1 + m);
  for (int i = 0; i < n; ++i) s[i] = a[i];
  s[n] = sep;
  for (int j = 0; j < m; ++j) s[n + 1 + j] = b[j];
  return s;
}
const int BASE = 1000 * 1000 * 1000 + 7;
const int MODULO = 1000 * 1000 * 1000 + 31;
template <int modulo>
inline int add(int a, int b) {
  return (a + b) % modulo;
}
template <int modulo>
inline int subtract(int a, int b) {
  return add<modulo>(a, modulo - b);
}
template <int modulo>
inline int multiply(long long a, long long b) {
  return (int)((a * b) % modulo);
}
struct DSU {
  vector<int> parents;
  vector<int> sizes;
  vector<int> ranks;
  DSU(size_t n = 1) { resize(n); }
  void resize(size_t n) {
    parents.resize(n);
    for (int v = 0; v < n; ++v) {
      parents[v] = v;
    }
    ranks.resize(n, 1);
    sizes.resize(n, 0);
  }
  int get(int v) {
    int parent = parents[v];
    if (parent == v) return v;
    return parents[v] = get(parent);
  }
  bool merge(int f, int t, int weight = 1, bool multiple_edges = false) {
    int a = get(f);
    int b = get(t);
    if (multiple_edges) {
      sizes[a] += weight;
    }
    if (a == b) return false;
    if (ranks[a] < ranks[b]) {
      swap(a, b);
    }
    parents[b] = a;
    if (ranks[a] == ranks[b]) ++ranks[a];
    sizes[a] += sizes[b];
    if (!multiple_edges) sizes[a] += weight;
    return true;
  }
  bool connected(int f, int t) { return get(f) == get(t); }
  int get_size(int v) { return sizes[get(v)]; }
};
class SegmentTree {
 public:
  int size;
  vector<long long> t;
  SegmentTree(int n) : size(n), t(size << 2, 0) {}
  void update_vertex(int v, int vL, int vR) { t[v] = t[vL] + t[vR]; }
  int index;
  long long value;
  void update_value(int _index, long long _value) {
    index = _index;
    value = _value;
    update_tree_index(1, 0, size);
  }
  void update_tree_index(int v, int left, int right) {
    if (left + 1 == right) {
      t[v] = value;
    } else {
      int mid = (left + right) >> 1;
      int vL = (v << 1), vR = (vL + 1);
      if (index < mid)
        update_tree_index(vL, left, mid);
      else
        update_tree_index(vR, mid, right);
      update_vertex(v, vL, vR);
    }
  }
  int get_prefix(long long _value) {
    value = _value;
    return get_tree_prefix(1, 0, size);
  }
  int get_tree_prefix(int v, int left, int right) {
    if (left + 1 == right) {
      return left;
    } else {
      int mid = (left + right) >> 1;
      int vL = (v << 1), vR = (vL + 1);
      long long left_value = t[vL];
      if (left_value < value) {
        value -= left_value;
        return get_tree_prefix(vR, mid, right);
      } else {
        return get_tree_prefix(vL, left, mid);
      }
    }
  }
};
class FenwickTree {
  int size;
  vector<long long> t;
  vector<long long> values;

 public:
  FenwickTree(int n) : size(n + 1), t(size, 0LL), values(size, 0LL) {}
  void update_tree_index(int index, long long delta) {
    for (; index < size; index += index & -index) {
      t[index] += delta;
    }
  }
  void update_value(int index, long long value) {
    ++index;
    long long delta = value - values[index];
    values[index] = value;
    update_tree_index(index, delta);
  }
  long long _sum;
  int get_prefix(long long value) {
    int result = 0;
    _sum = 0;
    for (int bit = 20; bit >= 0; --bit) {
      int next = result | (1 << bit);
      if (next < size && _sum + t[next] < value) {
        result = next;
        _sum += t[next];
      }
    }
    return result;
  }
};
template <int block_size>
class SqrtDecomposition {
  int size;
  vector<long long> blocks;
  vector<long long> values;

 public:
  SqrtDecomposition(int n) : size(n), blocks(size, 0LL), values(size, 0LL) {}
  void update_index(int index, long long delta) {
    int block = index / block_size;
    blocks[block] += delta;
  }
  void update_value(int index, long long value) {
    long long delta = value - values[index];
    values[index] = value;
    update_index(index, delta);
  }
  long long sum;
  int get_prefix(long long value) {
    int result = 0;
    sum = 0;
    for (int block = 0; block * block_size < size; ++block) {
      long long next_sum = sum + blocks[block];
      if (next_sum < value) {
        sum = next_sum;
      } else {
        result = block * block_size;
        break;
      }
    }
    while (result < size && sum + values[result] < value) {
      sum += values[result];
      ++result;
    }
    return result;
  }
};
const int MAX_K = 1e6 + 1;
int counts[MAX_K];
int get_answer(int n, vector<int> &a, int k, int d) {
  int answer = k;
  int unique = 0;
  for (int i = 0; i < n; ++i) {
    counts[a[i]]++;
    if (counts[a[i]] == 1) ++unique;
    if (i >= d) {
      counts[a[i - d]]--;
      if (counts[a[i - d]] == 0) --unique;
    }
    if (i >= d - 1) answer = min(answer, unique);
  }
  for (int i = 0; i < n; ++i) {
    counts[a[i]] = 0;
  }
  return answer;
}
vector<int> get_brute_answer(int n, int m,
                             vector<pair<int, int> > &friend_queries, int k,
                             vector<pair<int, int> > &edges, int q,
                             vector<vector<int> > &queries) {
  DSU dsu(n);
  map<int, vector<int> > friends;
  for (pair<int, int> &friend_query : friend_queries) {
    int f = friend_query.first - 1, t = friend_query.second - 1;
    friends[f].push_back(t);
    friends[t].push_back(f);
  }
  for (pair<int, int> &edge_query : edges) {
    int f = edge_query.first - 1, t = edge_query.second - 1;
    dsu.merge(f, t);
  }
  vector<int> answer;
  return answer;
}
FILE *print_file;
int print_test(int n, int m, vector<pair<int, int> > &friends, int k,
               vector<pair<int, int> > &edges, int q,
               vector<vector<int> > &queries, vector<int> &expected,
               vector<int> &actual, int bad_index) {
  fprintf(print_file, "%d %d %d\n", n, m, k);
  for (pair<int, int> &fq : friends) {
    fprintf(print_file, "%d %d\n", fq.first, fq.second);
  }
  for (pair<int, int> &eq : edges) {
    fprintf(print_file, "%d %d\n", eq.first, eq.second);
  }
  fprintf(print_file, "%d\n", q);
  fprintf(print_file, "===\n");
  for (int value : expected) {
    fprintf(print_file, "%d ", value);
  }
  fprintf(print_file, "\n");
  for (int value : actual) {
    fprintf(print_file, "%d ", value);
  }
  fprintf(print_file, "\n");
  fprintf(print_file, "%d\n", bad_index);
  fprintf(print_file, "===\n\n");
  return 1 + m + k + 1 + q + 1 + 1 + 1 + 1 + 1 + 1;
}
void set_print_file(const char *file_name) {
  print_file = fopen(file_name, "a");
}
void stress(int first_new_line = 1) {
  std::mt19937 rnd(time(0));
  std::uniform_int_distribution<> nGen(1, 20);
  std::uniform_int_distribution<> mGen(0, 10);
  std::uniform_int_distribution<> kGen(0, 10);
  int first_line = first_new_line;
  for (int it = 0; it < 10; ++it) {
    int n = nGen(rnd);
    int m = mGen(rnd);
    m = min(m, n * (n - 1) / 2);
    int k = kGen(rnd);
    k = min(k, n * (n - 1) / 2);
    std::uniform_int_distribution<> vGen(1, n);
    set<pair<int, int> > fp;
    vector<pair<int, int> > friends;
    for (int i = 0; i < m; ++i) {
      while (true) {
        int f = vGen(rnd);
        int t = vGen(rnd);
        if (f > t) swap(f, t);
        if (f != t && !fp.count({f, t})) {
          fp.insert({f, t});
          friends.push_back({f, t});
          break;
        }
      }
    }
    set<pair<int, int> > ep;
    vector<pair<int, int> > edges;
    for (int i = 0; i < k; ++i) {
      while (true) {
        int f = vGen(rnd);
        int t = vGen(rnd);
        if (f > t) swap(f, t);
        if (f != t && !ep.count({f, t})) {
          ep.insert({f, t});
          edges.push_back({f, t});
          break;
        }
      }
    }
    int q = 20;
    vector<vector<int> > queries(q);
    vector<int> expected =
        get_brute_answer(n, m, friends, k, edges, q, queries);
    vector<int> actual;
    int bad_index = -1;
    for (int i = 0; i < expected.size(); ++i) {
      if (expected[i] != actual[i]) {
        bad_index = i;
        break;
      }
    }
    if (bad_index >= 0) {
      std::cout << "Gotcha!" << SPACE << first_line << ENDL;
      first_line += print_test(n, m, friends, k, edges, q, queries, expected,
                               actual, bad_index);
    }
  }
  fclose(print_file);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tests = read_size();
  for (int t = 0; t < tests; ++t) {
    int n = read_size();
    int k = read_size();
    int d = read_size();
    vector<int> a;
    read_vector(a, n);
    int answer = get_answer(n, a, k, d);
    cout << answer << ENDL;
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

The only difference between easy and hard versions is constraints.

The BerTV channel every day broadcasts one episode of one of the k TV shows. You know the schedule for the next n days: a sequence of integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ k), where a_i is the show, the episode of which will be shown in i-th day.

The subscription to the show is bought for the entire show (i.e. for all its episodes), for each show the subscription is bought separately.

How many minimum subscriptions do you need to buy in order to have the opportunity to watch episodes of purchased shows d (1 ≤ d ≤ n) days in a row? In other words, you want to buy the minimum number of TV shows so that there is some segment of d consecutive days in which all episodes belong to the purchased shows.

Input

The first line contains an integer t (1 ≤ t ≤ 100) — the number of test cases in the input. Then t test case descriptions follow.

The first line of each test case contains three integers n, k and d (1 ≤ n ≤ 100, 1 ≤ k ≤ 100, 1 ≤ d ≤ n). The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ k), where a_i is the show that is broadcasted on the i-th day.

It is guaranteed that the sum of the values ​​of n for all test cases in the input does not exceed 100.

Output

Print t integers — the answers to the test cases in the input in the order they follow. The answer to a test case is the minimum number of TV shows for which you need to purchase a subscription so that you can watch episodes of the purchased TV shows on BerTV for d consecutive days. Please note that it is permissible that you will be able to watch more than d days in a row.

Example

Input


4
5 2 2
1 2 1 2 1
9 3 3
3 3 3 2 2 2 1 1 1
4 10 4
10 8 6 4
16 9 8
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3


Output


2
1
4
5

Note

In the first test case to have an opportunity to watch shows for two consecutive days, you need to buy a subscription on show 1 and on show 2. So the answer is two.

In the second test case, you can buy a subscription to any show because for each show you can find a segment of three consecutive days, consisting only of episodes of this show.

In the third test case in the unique segment of four days, you have four different shows, so you need to buy a subscription to all these four shows.

In the fourth test case, you can buy subscriptions to shows 3,5,7,8,9, and you will be able to watch shows for the last eight days.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
T read() {
  T value;
  cin >> value;
  return value;
}
int read_int() { return read<int>(); }
size_t read_size() { return read<size_t>(); }
long long read_ll() { return read<long long>(); }
string read_string() { return read<string>(); }
template <class T>
void read_vector(vector<T> &a, size_t size) {
  a.resize(size);
  for (T &value : a) cin >> value;
}
void read_pairs(vector<pair<int, int> > &a, size_t size) {
  a.resize(size);
  for (pair<int, int> &value : a) cin >> value.first >> value.second;
}
void read_iii(vector<pair<pair<int, int>, int> > &a, size_t size) {
  a.resize(size);
  for (pair<pair<int, int>, int> &value : a)
    cin >> value.first.first >> value.first.second >> value.second;
}
const char SPACE = ' ', ENDL = '\n';
template <class T>
void print(vector<T> &a, char sep = SPACE) {
  for (T &value : a) cout << value << sep;
  cout << '\n';
}
template <class T>
vector<int> compress(vector<T> &values) {
  vector<T> sorted = values;
  sort(sorted.begin(), sorted.end());
  sorted.resize(unique(sorted.begin(), sorted.end()) - sorted.begin());
  vector<int> result(values.size());
  for (int i = 0; i < values.size(); ++i) {
    result[i] =
        lower_bound(sorted.begin(), sorted.end(), values[i]) - sorted.begin();
  }
  return result;
}
int get_bit(long long mask, int bit) { return (int)((mask >> bit) & 1); }
string reverse(string s) {
  reverse(s.begin(), s.end());
  return s;
}
vector<int> reverse(vector<int> a) {
  reverse(a.begin(), a.end());
  return a;
}
vector<int> concat_separated(vector<int> &a, vector<int> &b, int sep = -1) {
  size_t n = a.size(), m = b.size();
  vector<int> s(n + 1 + m);
  for (int i = 0; i < n; ++i) s[i] = a[i];
  s[n] = sep;
  for (int j = 0; j < m; ++j) s[n + 1 + j] = b[j];
  return s;
}
const int BASE = 1000 * 1000 * 1000 + 7;
const int MODULO = 1000 * 1000 * 1000 + 31;
template <int modulo>
inline int add(int a, int b) {
  return (a + b) % modulo;
}
template <int modulo>
inline int subtract(int a, int b) {
  return add<modulo>(a, modulo - b);
}
template <int modulo>
inline int multiply(long long a, long long b) {
  return (int)((a * b) % modulo);
}
struct DSU {
  vector<int> parents;
  vector<int> sizes;
  vector<int> ranks;
  DSU(size_t n = 1) { resize(n); }
  void resize(size_t n) {
    parents.resize(n);
    for (int v = 0; v < n; ++v) {
      parents[v] = v;
    }
    ranks.resize(n, 1);
    sizes.resize(n, 0);
  }
  int get(int v) {
    int parent = parents[v];
    if (parent == v) return v;
    return parents[v] = get(parent);
  }
  bool merge(int f, int t, int weight = 1, bool multiple_edges = false) {
    int a = get(f);
    int b = get(t);
    if (multiple_edges) {
      sizes[a] += weight;
    }
    if (a == b) return false;
    if (ranks[a] < ranks[b]) {
      swap(a, b);
    }
    parents[b] = a;
    if (ranks[a] == ranks[b]) ++ranks[a];
    sizes[a] += sizes[b];
    if (!multiple_edges) sizes[a] += weight;
    return true;
  }
  bool connected(int f, int t) { return get(f) == get(t); }
  int get_size(int v) { return sizes[get(v)]; }
};
class SegmentTree {
 public:
  int size;
  vector<long long> t;
  SegmentTree(int n) : size(n), t(size << 2, 0) {}
  void update_vertex(int v, int vL, int vR) { t[v] = t[vL] + t[vR]; }
  int index;
  long long value;
  void update_value(int _index, long long _value) {
    index = _index;
    value = _value;
    update_tree_index(1, 0, size);
  }
  void update_tree_index(int v, int left, int right) {
    if (left + 1 == right) {
      t[v] = value;
    } else {
      int mid = (left + right) >> 1;
      int vL = (v << 1), vR = (vL + 1);
      if (index < mid)
        update_tree_index(vL, left, mid);
      else
        update_tree_index(vR, mid, right);
      update_vertex(v, vL, vR);
    }
  }
  int get_prefix(long long _value) {
    value = _value;
    return get_tree_prefix(1, 0, size);
  }
  int get_tree_prefix(int v, int left, int right) {
    if (left + 1 == right) {
      return left;
    } else {
      int mid = (left + right) >> 1;
      int vL = (v << 1), vR = (vL + 1);
      long long left_value = t[vL];
      if (left_value < value) {
        value -= left_value;
        return get_tree_prefix(vR, mid, right);
      } else {
        return get_tree_prefix(vL, left, mid);
      }
    }
  }
};
class FenwickTree {
  int size;
  vector<long long> t;
  vector<long long> values;

 public:
  FenwickTree(int n) : size(n + 1), t(size, 0LL), values(size, 0LL) {}
  void update_tree_index(int index, long long delta) {
    for (; index < size; index += index & -index) {
      t[index] += delta;
    }
  }
  void update_value(int index, long long value) {
    ++index;
    long long delta = value - values[index];
    values[index] = value;
    update_tree_index(index, delta);
  }
  long long _sum;
  int get_prefix(long long value) {
    int result = 0;
    _sum = 0;
    for (int bit = 20; bit >= 0; --bit) {
      int next = result | (1 << bit);
      if (next < size && _sum + t[next] < value) {
        result = next;
        _sum += t[next];
      }
    }
    return result;
  }
};
template <int block_size>
class SqrtDecomposition {
  int size;
  vector<long long> blocks;
  vector<long long> values;

 public:
  SqrtDecomposition(int n) : size(n), blocks(size, 0LL), values(size, 0LL) {}
  void update_index(int index, long long delta) {
    int block = index / block_size;
    blocks[block] += delta;
  }
  void update_value(int index, long long value) {
    long long delta = value - values[index];
    values[index] = value;
    update_index(index, delta);
  }
  long long sum;
  int get_prefix(long long value) {
    int result = 0;
    sum = 0;
    for (int block = 0; block * block_size < size; ++block) {
      long long next_sum = sum + blocks[block];
      if (next_sum < value) {
        sum = next_sum;
      } else {
        result = block * block_size;
        break;
      }
    }
    while (result < size && sum + values[result] < value) {
      sum += values[result];
      ++result;
    }
    return result;
  }
};
const int MAX_K = 1e6 + 1;
int counts[MAX_K];
int get_answer(int n, vector<int> &a, int k, int d) {
  int answer = k;
  int unique = 0;
  for (int i = 0; i < n; ++i) {
    counts[a[i]]++;
    if (counts[a[i]] == 1) ++unique;
    if (i >= d) {
      counts[a[i - d]]--;
      if (counts[a[i - d]] == 0) --unique;
    }
    if (i >= d - 1) answer = min(answer, unique);
  }
  for (int i = 0; i < n; ++i) {
    counts[a[i]] = 0;
  }
  return answer;
}
vector<int> get_brute_answer(int n, int m,
                             vector<pair<int, int> > &friend_queries, int k,
                             vector<pair<int, int> > &edges, int q,
                             vector<vector<int> > &queries) {
  DSU dsu(n);
  map<int, vector<int> > friends;
  for (pair<int, int> &friend_query : friend_queries) {
    int f = friend_query.first - 1, t = friend_query.second - 1;
    friends[f].push_back(t);
    friends[t].push_back(f);
  }
  for (pair<int, int> &edge_query : edges) {
    int f = edge_query.first - 1, t = edge_query.second - 1;
    dsu.merge(f, t);
  }
  vector<int> answer;
  return answer;
}
FILE *print_file;
int print_test(int n, int m, vector<pair<int, int> > &friends, int k,
               vector<pair<int, int> > &edges, int q,
               vector<vector<int> > &queries, vector<int> &expected,
               vector<int> &actual, int bad_index) {
  fprintf(print_file, "%d %d %d\n", n, m, k);
  for (pair<int, int> &fq : friends) {
    fprintf(print_file, "%d %d\n", fq.first, fq.second);
  }
  for (pair<int, int> &eq : edges) {
    fprintf(print_file, "%d %d\n", eq.first, eq.second);
  }
  fprintf(print_file, "%d\n", q);
  fprintf(print_file, "===\n");
  for (int value : expected) {
    fprintf(print_file, "%d ", value);
  }
  fprintf(print_file, "\n");
  for (int value : actual) {
    fprintf(print_file, "%d ", value);
  }
  fprintf(print_file, "\n");
  fprintf(print_file, "%d\n", bad_index);
  fprintf(print_file, "===\n\n");
  return 1 + m + k + 1 + q + 1 + 1 + 1 + 1 + 1 + 1;
}
void set_print_file(const char *file_name) {
  print_file = fopen(file_name, "a");
}
void stress(int first_new_line = 1) {
  std::mt19937 rnd(time(0));
  std::uniform_int_distribution<> nGen(1, 20);
  std::uniform_int_distribution<> mGen(0, 10);
  std::uniform_int_distribution<> kGen(0, 10);
  int first_line = first_new_line;
  for (int it = 0; it < 10; ++it) {
    int n = nGen(rnd);
    int m = mGen(rnd);
    m = min(m, n * (n - 1) / 2);
    int k = kGen(rnd);
    k = min(k, n * (n - 1) / 2);
    std::uniform_int_distribution<> vGen(1, n);
    set<pair<int, int> > fp;
    vector<pair<int, int> > friends;
    for (int i = 0; i < m; ++i) {
      while (true) {
        int f = vGen(rnd);
        int t = vGen(rnd);
        if (f > t) swap(f, t);
        if (f != t && !fp.count({f, t})) {
          fp.insert({f, t});
          friends.push_back({f, t});
          break;
        }
      }
    }
    set<pair<int, int> > ep;
    vector<pair<int, int> > edges;
    for (int i = 0; i < k; ++i) {
      while (true) {
        int f = vGen(rnd);
        int t = vGen(rnd);
        if (f > t) swap(f, t);
        if (f != t && !ep.count({f, t})) {
          ep.insert({f, t});
          edges.push_back({f, t});
          break;
        }
      }
    }
    int q = 20;
    vector<vector<int> > queries(q);
    vector<int> expected =
        get_brute_answer(n, m, friends, k, edges, q, queries);
    vector<int> actual;
    int bad_index = -1;
    for (int i = 0; i < expected.size(); ++i) {
      if (expected[i] != actual[i]) {
        bad_index = i;
        break;
      }
    }
    if (bad_index >= 0) {
      std::cout << "Gotcha!" << SPACE << first_line << ENDL;
      first_line += print_test(n, m, friends, k, edges, q, queries, expected,
                               actual, bad_index);
    }
  }
  fclose(print_file);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tests = read_size();
  for (int t = 0; t < tests; ++t) {
    int n = read_size();
    int k = read_size();
    int d = read_size();
    vector<int> a;
    read_vector(a, n);
    int answer = get_answer(n, a, k, d);
    cout << answer << ENDL;
  }
  return 0;
}

```