A-Gamer Hemose

One day, Ahmed_Hossam went to Hemose and said "Let's solve a gym contest!". Hemose didn't want to do that, as he was playing Valorant, so he came up with a problem and told it to Ahmed to distract him. Sadly, Ahmed can't solve it... Could you help him?

There is an Agent in Valorant, and he has nn weapons. The ii-th weapon has a damage value aiai, and the Agent will face an enemy whose health value is HH.

The Agent will perform one or more moves until the enemy dies.

In one move, he will choose a weapon and decrease the enemy's health by its damage value. The enemy will die when his health will become less than or equal to 00. However, not everything is so easy: the Agent can't choose the same weapon for 22 times in a row.

What is the minimum number of times that the Agent will need to use the weapons to kill the enemy?

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤105)(1≤t≤105). Description of the test cases follows.

The first line of each test case contains two integers nn and HH (2≤n≤103,1≤H≤109)(2≤n≤103,1≤H≤109) — the number of available weapons and the initial health value of the enemy.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤109)(1≤ai≤109) — the damage values of the weapons.

It's guaranteed that the sum of nn over all test cases doesn't exceed 2⋅1052⋅105.

Output

For each test case, print a single integer — the minimum number of times that the Agent will have to use the weapons to kill the enemy.

Example

Input

3
2 4
3 7
2 6
4 2
3 11
2 1 7

Output

1
2
3

Note

In the first test case, the Agent can use the second weapon, making health value of the enemy equal to 4−7=−34−7=−3. −3≤0−3≤0, so the enemy is dead, and using weapon 11 time was enough.

In the second test case, the Agent can use the first weapon first, and then the second one. After this, the health of enemy will drop to 6−4−2=06−4−2=0, meaning he would be killed after using weapons 22 times.

In the third test case, the Agent can use the weapons in order (third, first, third), decreasing the health value of enemy to 11−7−2−7=−511−7−2−7=−5 after using the weapons 33 times. Note that we can't kill the enemy by using the third weapon twice, as even though 11−7−7<011−7−7<0, it's not allowed to use the same weapon twice in a row.

题意：

给你n个数，和一个数h，每一次从n个数中选一个数a执行h-=a;不能连续两次选同一个数，问最少多少次使得h<=0.

思路：

找到最大的两个数轮流使用即可。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,h;
        int a[10000];
        cin>>n>>h;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        sort(a,a+n,cmp);
        int ans=0;
        int sum=a[0]+a[1];
        ans+=h/sum*2;
        if(h%sum)
            ans+=1;
        if(h%sum>a[0])
            ans+=1;
        cout<<ans<<endl;
    }
}

B-Hemose Shopping

Hemose was shopping with his friends Samez, AhmedZ, AshrafEzz, TheSawan and O_E in Germany. As you know, Hemose and his friends are problem solvers, so they are very clever. Therefore, they will go to all discount markets in Germany.

Hemose has an array of nn integers. He wants Samez to sort the array in the non-decreasing order. Since it would be a too easy problem for Samez, Hemose allows Samez to use only the following operation:

• Choose indices ii and jj such that 1≤i,j≤n1≤i,j≤n, and |i−j|≥x|i−j|≥x. Then, swap elements aiai and ajaj.

Can you tell Samez if there's a way to sort the array in the non-decreasing order by using the operation written above some finite number of times (possibly 00)?

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤105)(1≤t≤105). Description of the test cases follows.

The first line of each test case contains two integers nn and xx (1≤x≤n≤105)(1≤x≤n≤105).

The second line of each test case contains nn integers a1,a2,...,ana1,a2,...,an (1≤ai≤109)(1≤ai≤109).

It is guaranteed that the sum of nn over all test cases doesn't exceed 2⋅1052⋅105.

Output

For each test case, you should output a single string.

If Samez can sort the array in non-decreasing order using the operation written above, output "YES" (without quotes). Otherwise, output "NO" (without quotes).

You can print each letter of "YES" and "NO" in any case (upper or lower).

Example

Input

4
3 3
3 2 1
4 3
1 2 3 4
5 2
5 1 2 3 4
5 4
1 2 3 4 4

Output

NO
YES
YES
YES

Note

In the first test case, you can't do any operations.

In the second test case, the array is already sorted.

In the third test case, you can do the operations as follows:

• [5,1,2,3,4][5,1,2,3,4], swap(a1,a3)swap(a1,a3)
• [2,1,5,3,4][2,1,5,3,4], swap(a2,a5)swap(a2,a5)
• [2,4,5,3,1][2,4,5,3,1], swap(a2,a4)swap(a2,a4)
• [2,3,5,4,1][2,3,5,4,1], swap(a1,a5)swap(a1,a5)
• [1,3,5,4,2][1,3,5,4,2], swap(a2,a5)swap(a2,a5)
• [1,2,5,4,3][1,2,5,4,3], swap(a3,a5)swap(a3,a5)
• [1,2,3,4,5][1,2,3,4,5]

(Here swap(ai,aj)swap(ai,aj) refers to swapping elements at positions ii, jj).

题意：给你一个数组a[n]，整数k，执行给定的规则能否使a[n]升序排列

规则：

可以交换a[i]和a[j],当且仅当1≤i,j≤n and |i−j|≥x

思路：

当n>=2*x，所有位置都能交换，可以使a[n]升序排列

否则，只有当[n-x,x-1]之间的所有数不需要移动时，才能使a[n]升序排列。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[10000500];
ll b[10000500];
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {

        ll n,x;
        cin>>n>>x;
        for(ll i=0;i<n;i++)
        {
            cin>>a[i];
            b[i]=a[i];
        }
        sort(b,b+n);
        if(n>=2*x)
        {
            cout<<"YES"<<endl;
            continue;
        }
        ll flag=1;
        for(ll i=n-x;i<=x-1;i++)
        {
            if(a[i]!=b[i])
            {
                cout<<"NO"<<endl;
                flag=0;
                break;
            }
        }
        if(flag==1)
        {
            cout<<"YES"<<endl;
            continue;
        }

    }
}