407923: GYM102942 F Offer

Steve has $$$k$$$ dollars and he wants to buy some items from a shop. This shop has $$$n$$$ elements arranged in a row. For a given $$$i (1 \leq i \leq n)$$$, the rate of the $$$i^{th}$$$ item is $$$a_i$$$.

The shop has a weird rule. A customer can only buy the items that form a contiguous segment, that is, they will choose two integers $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r\leq n)$$$ and buy all the items in the subsegment $$$[l,r]$$$.

A subsegment $$$[l, r] \: (l ≤ r)$$$ of array $$$a$$$ is the sequence $$$a_l, a_{l + 1}, \dots, a_r$$$.

Today the shop has a special offer. If a customer buys an item of some rate, then all other items in the selected range with the same rate can be bought for free.

Find the maximum number of items that Steve can buy with $$$k$$$ dollars by visiting the shop only once.

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^{2})$$$ $$$-$$$ the number of test cases in the input.

Then $$$t$$$ test cases follow.

The first line of the test case contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq 2\cdot10^{5},1 \leq k \leq 10^{6})$$$$$$-$$$ number of items in the shop and amount of dollars Steve has.

The second line of the test case contains $$$n$$$ space-separated integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^{6})$$$$$$-$$$ $$$a_i$$$ is the $$$i^{th}$$$ item's rate as dollar.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2\cdot10^{5}(\sum n \leq 2\cdot10^{5})$$$.

For each test case, Print the maximum number of items Steve can buy.

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

5
8
3

In the first test case, Steve can get the items in the range $$$a[2\dots6]$$$ by buying the $$$2^{nd}$$$ and $$$3^{rd}$$$ items.

In the second test, Steve can get all the items just by buying the $$$1^{st}$$$, $$$3^{rd}$$$ and $$$6^{th}$$$ items.