Consider a sequence of integers a_1, a_2, …, a_n. In one move, you can select any element of the sequence and delete it. After an element is deleted, all elements to the right are shifted to the left by 1 position, so there are no empty spaces in the sequence. So after you make a move, the sequence's length decreases by 1. The indices of the elements after the move are recalculated.

E. g. let the sequence be a=[3, 2, 2, 1, 5]. Let's select the element a_3=2 in a move. Then after the move the sequence will be equal to a=[3, 2, 1, 5], so the 3-rd element of the new sequence will be a_3=1 and the 4-th element will be a_4=5.

You are given a sequence a_1, a_2, …, a_n and a number k. You need to find the minimum number of moves you have to make so that in the resulting sequence there will be at least k elements that are equal to their indices, i. e. the resulting sequence b_1, b_2, …, b_m will contain at least k indices i such that b_i = i.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

Each test case consists of two consecutive lines. The first line contains two integers n and k (1 ≤ k ≤ n ≤ 2000). The second line contains a sequence of integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n). The numbers in the sequence are not necessarily different.

It is guaranteed that the sum of n over all test cases doesn't exceed 2000.

Output

For each test case output in a single line:

  * -1 if there's no desired move sequence; 
  * otherwise, the integer x (0 ≤ x ≤ n) — the minimum number of the moves to be made so that the resulting sequence will contain at least k elements that are equal to their indices. 

Example

Input


4
7 6
1 1 2 3 4 5 6
5 2
5 1 3 2 3
5 2
5 5 5 5 4
8 4
1 2 3 3 2 2 5 5


Output


1
2
-1
2

Note

In the first test case the sequence doesn't satisfy the desired condition, but it can be provided by deleting the first element, hence the sequence will be [1, 2, 3, 4, 5, 6] and 6 elements will be equal to their indices.

In the second test case there are two ways to get the desired result in 2 moves: the first one is to delete the 1-st and the 3-rd elements so that the sequence will be [1, 2, 3] and have 3 elements equal to their indices; the second way is to delete the 2-nd and the 3-rd elements to get the sequence [5, 2, 3] with 2 desired elements.
#include<bits/stdc++.h>		
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pr;
typedef vector<pair<int,int> > vpr;
typedef vector<vi> vvi;
#define ff first
#define ss second
#define fort(i,m,n) for(int i=m;i<n;i++)
#define fora(arr,n) for(int i=0;i<n;i++) cin>>arr[i];
#define begud(k) cerr<<"\t-->"<<#k<<" = "<<k<<"\n";
#define debug(args...) { string _debug_list = #args; replace(_debug_list.begin(), _debug_list.end(), ',', ' '); stringstream _debug_stream(_debug_list); istream_iterator<string> __it(_debug_stream); debug_func(__it, args); }
#define endl "\n"
#define pb push_back
/* 
// What follows is a magical ordered set data structure.
// Supports the following functions:
// find_by_order(int k) - returns k'th smallest element (0-indexed)
// order_of_key(int k) - returns number of elements strictly smaller than k.
using namespace __gnu_pbds;
#define ordered_set tree <ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
 */
const int mod = 1e9 + 7, mod2 = 998244353;
void debug_func(istream_iterator<string> _it) {
	cerr << "\n";
} 
template <typename T, typename... Args>
void debug_func(istream_iterator<string> _it, T x, Args... args) {
	cerr << "[ " << *_it << " : " << x << " ]";
	cerr << " , ";
	debug_func(++_it, args...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
long long true_rand(long long n) {
	// Returns a random number between 0 and n - 1 inclusive using mt19937.
	uniform_int_distribution<long long> uid(0, n - 1);
	return uid(rng);
}
ll power(ll a,ll b)
{
	a = a % mod;
	if(a == 0)
		return 0;
	ll ans = 1;
	while(b)
	{
		if(b & 1)
			ans = (ans * a) % mod;
		a = (a * a) % mod;
		b = b >> 1;
	}
	return ans;
}
template<typename T>
bool sortbysec(const pair<T,T> &a,const pair<T,T> &b)                
{
	return (a.second < b.second); 
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	while(t--)
	{
		int n, k;
		cin >> n >> k;
		vi a(n);
		fora(a, n);
		int dp[n][n + 1] = {}; // number of elements that match to their indices till index i with j deletions before it
		if(a[0] == 1)
			dp[0][0] = 1;
		fort(i, 1, n)
		{
			int to_remove = (i + 1) - a[i];
			fort(j, 0, n + 1)
			{
				dp[i][j] = dp[i - 1][j];
				if(j == to_remove)
				{
					dp[i][j] += ((j >= 1)? dp[i - 1][j - 1] : 0) + ((j >= 2)? (dp[i - 1][j - 2] + 1) : 0);
					if(!j)
						dp[i][j]++;
				}
			}
		}
		int mn = -1;
		fort(i, 0, n + 1)
		{
			if(dp[n - 1][i] >= k)
			{
				mn = i;
				break;
			}
		}
		cout << mn << endl;
	}
    return 0;
}