SOLVE

LATER

Stranger Things

Problem

Editorial

Analytics

Stranger Things have started happening in the town of Hawkins, Indiana after Will Byers disappeared last week. Will's friends Dustin, Mike, and Lucas discover a psychokinetic girl, Eleven who claims to know Will's location.

They gather total *N* kids from neighbourhood (including them with their special monster killing guns and went at the location given by Eleven. As soon as they reach the place, they find an army of *K* deadly monsters ready to kill whatever comes in their way. Eleven uses her psychic powers and finds a way to kill some of the monsters.

A monster can be killed by a kid's gun if and only if the power of monster is divisible by the gun's power.
Monster are numbered from *1* to *K* and the power of \(ith\) monster is *i*. The power of the gun \(i^{th}\) kid is holding is \(a[i]\).

Find the maximum number of monsters the kids will be able to kill.

**Input:**

First line of input consist of a single integer *T* denoting the total number of test case. *T* test cases follow.

The first line of test case contains a single integer *N* denoting the number of kids.

Second line of test case contains *N* space separated integers denoting the power of gun \(ith\) kid is holding.

Third line of test case contains a single integer *K* representing the army of monsters.

**Output**

For each test case output a single integer in new line representing the maximum number of monsters the kids will be able to kill.

**Subtask 1: \(10\) Points**

\( 1\le T \le 100 \)

\( 1\le N \le 12 \)

\( 1\le a[i] \le 20 \)

\( 1\le K \le 1000 \)

**Subtask 2: \(30\) Points**

\( 1\le T \le 100 \)

\( N=3 \)

\( a[]=[2,3,5] \)

\( 1\le K \le 10^{18} \)

**Subtask 3: \(60\) Points**

\( 1\le T \le 100 \)

\( 1\le N \le 12 \)

\( 1\le a[i] \le 20 \)

\( 1\le K \le 10^{18} \)

Explanation

There are 10 monsters having powers 1,2,3,4,5,6,7,8,9,10. only {2,4,5,6,8,10} are the monsters than can be killed with guns with power{2,5}

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Swift-4.1,
Visual Basic

Initializing Code Editor...

{"94e873e": "/pagelets/problems-hint/algorithm/thl-cake1/", "1f55910": "/pagelets/suggested-problems/algorithm/thl-cake1/", "f3b06fd": "/pagelets/problem-author-tester/algorithm/thl-cake1/", "5edf08c": "/pagelets/show-submission/algorithm/thl-cake1/", "4bb9c95": "/pagelets/recommended-problems/algorithm/thl-cake1/"}

realtime.hackerearth.com

80

f23bd1d691284101ff6a051666272ae715dd1d23

58a29e5cae2309f04b28

/realtime/pusher/auth/