Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

F. Valuable Cards
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In his favorite cafe Kmes once again wanted to try the herring under a fur coat. Previously, it would not have been difficult for him to do this, but the cafe recently introduced a new purchasing policy.

Now, in order to make a purchase, Kmes needs to solve the following problem: n cards with prices for different positions are laid out in front of him, on the i-th card there is an integer ai, among these prices there is no whole positive integer x.

Kmes is asked to divide these cards into the minimum number of bad segments (so that each card belongs to exactly one segment). A segment is considered bad if it is impossible to select a subset of cards with a product equal to x. All segments, in which Kmes will divide the cards, must be bad.

Formally, the segment (l,r) is bad if there are no indices i1<i2<<ik such that li1,ikr, and ai1ai2aik=x.

Help Kmes determine the minimum number of bad segments in order to enjoy his favorite dish.

Input

The first line contains a single integer t (1t103) — the number of test cases.

The first line of each set of input data gives you 2 integers n and x (1n105,2x105) — the number of cards and the integer, respectively.

The second line of each set of input data contains n integers ai (1ai2105,aix) — the prices on the cards.

It is guaranteed that the sum of n over all sets of test data does not exceed 105.

Output

For each set of input data, output the minimum number of bad segments.

Example
Input
8
6 4
2 3 6 2 1 2
9 100000
50000 25000 12500 6250 3125 2 4 8 16
5 2
1 1 1 1 1
8 6
4 3 4 3 4 3 4 3
7 12
6 11 1 3 11 10 2
10 5
2 4 4 2 4 4 4 3 1 1
7 8
4 6 5 1 2 4 1
8 27
3 9 17 26 2 20 9 3
Output
3
2
1
1
2
1
3
3