目录

A-Nearest Interesting Number

题意：

思路：

代码：

B-Equalize Prices

题意：

思路：

代码：

C-Computer Game

题意：

思路：

代码：

D-Candy Box (easy version)

题意：

思路：

代码：

A-Nearest Interesting Number

Polycarp knows that if the sum of the digits of a number is divisible by 33, then the number itself is divisible by 33. He assumes that the numbers, the sum of the digits of which is divisible by 44, are also somewhat interesting. Thus, he considers a positive integer nn interesting if its sum of digits is divisible by 44.

Help Polycarp find the nearest larger or equal interesting number for the given number aa. That is, find the interesting number nn such that n \ge an≥a and nn is minimal.

Input

The only line in the input contains an integer aa (1 \le a \le 10001≤a≤1000).

Output

Print the nearest greater or equal interesting number for the given number aa. In other words, print the interesting number nn such that n \ge an≥a and nn is minimal.

Examples

Input

432

Output

435

Input

99

Output

103

Input

237

Output

237

Input

42

Output

44

题意：

定义有趣的数：如果一个正整数的每位数相加得到的结果能被四整除，那么这个正整数就是有趣的数。

输入一个数，输出大于或等于这个数的最小的有趣数。

思路：

直接判断即可

代码：

#include<iostream>
using namespace std;
int sum(int a)
{
    int ans=0;
    while(a)
    {
        ans+=a%10;
        a/=10;
    }
    return ans;
}
int main()
{
    int a;
    cin>>a;
    while(sum(a)%4)
    {
        a++;
    }
    cout<<a<<endl;
}

B-Equalize Prices

There are nn products in the shop. The price of the ii-th product is a_iai​. The owner of the shop wants to equalize the prices of all products. However, he wants to change prices smoothly.

In fact, the owner of the shop can change the price of some product ii in such a way that the difference between the old price of this product a_iai​ and the new price b_ibi​ is at most kk. In other words, the condition |a_i - b_i| \le k∣ai​−bi​∣≤k should be satisfied (|x|∣x∣ is the absolute value of xx).

He can change the price for each product not more than once. Note that he can leave the old prices for some products. The new price b_ibi​ of each product ii should be positive (i.e. b_i > 0bi​>0 should be satisfied for all ii from 11 to nn).

Your task is to find out the maximum possible equal price BB of all productts with the restriction that for all products the condiion |a_i - B| \le k∣ai​−B∣≤k should be satisfied (where a_iai​ is the old price of the product and BB is the same new price of all products) or report that it is impossible to find such price BB.

Note that the chosen price BB should be integer.

You should answer qq independent queries.

Input

The first line of the input contains one integer qq (1 \le q \le 1001≤q≤100) — the number of queries. Each query is presented by two lines.

The first line of the query contains two integers nn and kk (1 \le n \le 100, 1 \le k \le 10^81≤n≤100,1≤k≤108) — the number of products and the value kk. The second line of the query contains nn integers a_1, a_2, \dots, a_na1​,a2​,…,an​ (1 \le a_i \le 10^81≤ai​≤108), where a_iai​ is the price of the ii-th product.

Output

Print qq integers, where the ii-th integer is the answer BB on the ii-th query.

If it is impossible to equalize prices of all given products with restriction that for all products the condition |a_i - B| \le k∣ai​−B∣≤k should be satisfied (where a_iai​ is the old price of the product and BB is the new equal price of all products), print -1. Otherwise print the maximum possible equal price of all products.

Example

Input

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

Output

2
6
-1
7

Note

In the first example query you can choose the price B=2B=2. It is easy to see that the difference between each old price and each new price B=2B=2 is no more than 11.

In the second example query you can choose the price B=6B=6 and then all the differences between old and new price B=6B=6 will be no more than 22.

In the third example query you cannot choose any suitable price BB. For any value BB at least one condition out of two will be violated: |1-B| \le 2∣1−B∣≤2, |6-B| \le 2∣6−B∣≤2.

In the fourth example query all values BB between 11 and 77 are valid. But the maximum is 77, so it's the answer.

题意：

给你n个老价格，现在需要定一个新价格使得所有老价格与新价格差的绝对值小于等于k，问新价格的最大值，没有满足条件的输出-1。

思路：

老价格的最大、最小值之差如果大于2*k肯定输出-1，否则输出最小值+k。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        int a[200];
        int n,k;
        cin>>n>>k;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        sort(a,a+n);
        if(a[n-1]-a[0]>2*k)
            cout<<-1<<endl;
        else
            cout<<a[0]+k<<endl;
    }

}

C-Computer Game

Vova is playing a computer game. There are in total nn turns in the game and Vova really wants to play all of them. The initial charge of his laptop battery (i.e. the charge before the start of the game) is kk.

During each turn Vova can choose what to do:

• If the current charge of his laptop battery is strictly greater than aa, Vova can just play, and then the charge of his laptop battery will decrease by aa;
• if the current charge of his laptop battery is strictly greater than bb (b<ab<a), Vova can play and charge his laptop, and then the charge of his laptop battery will decrease by bb;
• if the current charge of his laptop battery is less than or equal to aa and bb at the same time then Vova cannot do anything and loses the game.

Regardless of Vova's turns the charge of the laptop battery is always decreases.

Vova wants to complete the game (Vova can complete the game if after each of nn turns the charge of the laptop battery is strictly greater than 00). Vova has to play exactly nn turns. Among all possible ways to complete the game, Vova wants to choose the one where the number of turns when he just plays (first type turn) is the maximum possible. It is possible that Vova cannot complete the game at all.

Your task is to find out the maximum possible number of turns Vova can just play (make the first type turn) or report that Vova cannot complete the game.

You have to answer qq independent queries.

Input

The first line of the input contains one integer qq (1 \le q \le 10^51≤q≤105) — the number of queries. Each query is presented by a single line.

The only line of the query contains four integers k, n, ak,n,a and bb (1 \le k, n \le 10^9, 1 \le b < a \le 10^91≤k,n≤109,1≤b<a≤109) — the initial charge of Vova's laptop battery, the number of turns in the game and values aa and bb, correspondingly.

Output

For each query print one integer: -1 if Vova cannot complete the game or the maximum number of turns Vova can just play (make the first type turn) otherwise.

Example

Input

6
15 5 3 2
15 5 4 3
15 5 2 1
15 5 5 1
16 7 5 2
20 5 7 3

Output

4
-1
5
2
0
1

Note

In the first example query Vova can just play 44 turns and spend 1212 units of charge and then one turn play and charge and spend 22 more units. So the remaining charge of the battery will be 11.

In the second example query Vova cannot complete the game because even if he will play and charge the battery during each turn then the charge of the laptop battery will be 00 after the last turn.

题意：

给你四个数k,n,a,b；n次操作，每次执行k-=a或者k-=b，并且k要一直严格大于0，输出满足条件的的操作中k-=a的执行次数最多是多少。

思路：

先执行执行n次k-=b,如果k<=0,则没有满足条件的情况，输出-1；如果k>0，则用(k-n*b-1)/(a-b)来算出最多可以把多少个k-=b换成k-=a,如果超过n个就输出n,否则输出(k-n*b-1)/(a-b)，注意要用long long。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
    ll q;
    cin>>q;
    while(q--)
    {
        ll k,n,a,b;
        cin>>k>>n>>a>>b;
        if(n*b>=k)
        {
            cout<<-1<<endl;
            continue;
        }
        cout<<min((k-n*b-1)/(a-b),n)<<endl;;
    }

}

D-Candy Box (easy version)

This problem is actually a subproblem of problem G from the same contest.

There are nn candies in a candy box. The type of the ii-th candy is a_iai​ (1 \le a_i \le n1≤ai​≤n).

You have to prepare a gift using some of these candies with the following restriction: the numbers of candies of each type presented in a gift should be all distinct (i. e. for example, a gift having two candies of type 11 and two candies of type 22 is bad).

It is possible that multiple types of candies are completely absent from the gift. It is also possible that not all candies of some types will be taken to a gift.

Your task is to find out the maximum possible size of the single gift you can prepare using the candies you have.

You have to answer qq independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains one integer qq (1 \le q \le 2 \cdot 10^51≤q≤2⋅105) — the number of queries. Each query is represented by two lines.

The first line of each query contains one integer nn (1 \le n \le 2 \cdot 10^51≤n≤2⋅105) — the number of candies.

The second line of each query contains nn integers a_1, a_2, \dots, a_na1​,a2​,…,an​ (1 \le a_i \le n1≤ai​≤n), where a_iai​ is the type of the ii-th candy in the box.

It is guaranteed that the sum of nn over all queries does not exceed 2 \cdot 10^52⋅105.

Output

For each query print one integer — the maximum possible size of the single gift you can compose using candies you got in this query with the restriction described in the problem statement.

Example

Input

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

Output

3
10
9

Note

In the first query, you can prepare a gift with two candies of type 88 and one candy of type 55, totalling to 33 candies.

Note that this is not the only possible solution — taking two candies of type 44 and one candy of type 66 is also valid.

题意：

有n个糖果，输入每个糖果的类型，不同的数字代表不同的类型，现在要送出糖果并满足：不同种类的糖果数量不同；问最多送多少糖果。

思路：

对每种糖果的数量降序排序，第一个是最多的数量肯定要，后面每一个和前一个的数量比较，如果相等就让当前种类糖果数量减一，如果前一个小于当前(多种糖果数相等的情况)，就取当前数量为前一个的数量减一；最后所有大于0的数量累加输出。

代码：

#include<iostream>
#include<algorithm>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
#include<cstdlib>
using namespace std;
typedef long long ll;
bool cmp(ll a,ll b)
{
    return a>b;
}
int main()
{
    ll q;
    cin>>q;
    while(q--)
    {
        ll n;
        cin>>n;
        map<ll,ll> mp;
        vector<ll> ve;
        for(ll i=0;i<n;i++)
        {
            ll t;
            cin>>t;
            if(mp.find(t)==mp.end())
            {
                mp[t]=1;
            }
            else
            {
                mp[t]+=1;
            }
        }
        map<ll,ll>::iterator it;
        for(it=mp.begin();it!=mp.end();it++)
        {
            ve.push_back(it->second);
        }
        sort(ve.begin(),ve.end(),cmp);
        int ans=ve[0];
        for(int i=1;i<ve.size();i++)
        {
            if(ve[i]==ve[i-1])
            {
                ve[i]-=1;
            }
            else if(ve[i]>ve[i-1])
            {
                ve[i]=ve[i-1]-1;
            }
            if(ve[i]>0)
            {
                ans+=ve[i];
            }
            else
                break;
        }
        cout<<ans<<endl;
    }

}