409374: GYM103492 L Contest Remake

Memory Limit:512 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Contest Remaketime limit per test8.0 smemory limit per test512 megabytesinputstandard inputoutputstandard output

The annual Chengdu Children Poker Contest (CCPC) has begun! Unfortunately, the cards have been all blown away during the contest and the contest cannot go ahead. You, as the contest organizer, need to prepare a rematch and reproduce a pack of cards for the rematch.

The cards used in the contest are quite special — each card represents a set of integers. For a pack of $$$m$$$ cards, we denote the set represented by each card as $$$S_1,S_2,\dots,S_m$$$. The pack of the cards should meet the following conditions:

  • The elements in each set are unordered and distinct.
  • For every $$$i$$$, $$$S_i \subset \mathbb{Z}^+$$$ (the set of all positive integers), and $$$S_i \neq \emptyset$$$.
  • For every $$$1 \le i < j \le m$$$, $$$S_i \neq S_j$$$.
  • For every $$$i$$$, $$$\prod_{x \in S_i}x \le C$$$, where $$$C$$$ is a given constant.

What's more, a mystery guy tells you the reason why the cards are blown away is that you use some ominous integers. There are $$$n$$$ ominous integers, and you should avoid using them in case your cards get blown away again. We denote the set of ominous integers as $$$T$$$. That is:

  • For every $$$i$$$, $$$S_i \cap T=\emptyset$$$.

You want to reproduce as many cards as possible. Now given $$$C$$$ and the $$$n$$$ ominous integers, please calculate the maximum number of cards in the pack.

Input

The first line contains a positive integer $$$T$$$ $$$(1\le T \le 20)$$$, indicating the number of test cases.

For each test case, the first line contains two integers $$$n, C$$$ $$$(0\le n\le 10^{5},1\le C \le 10^{9})$$$, indicating the number of ominous integers and the given constant.

The second line contains $$$n$$$ positive integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\le a_i \le C)$$$, indicating the ominous integers. It is guaranteed that all the $$$n$$$ integers are distinct.

It is guaranteed that $$$\sum n\le 7\times 10^5$$$, and there are at most $$$10$$$ test cases that meet $$$C>10^6$$$.

Output

For each test case, print one integer in a single line, indicating the maximum number of cards in the pack.

ExampleInput
2
1 6
3
2 10
3 5
Output
9
17

加入题单

上一题 下一题 算法标签: