Sorrow and Anger... I'll Factor Them All!

Yuuka

The members of Veritas finished my work while I was asleep. All that's left now is the equipment management plan Noa gave me. Let's calculate this quickly and finish preparing for the sports festival.

I've numbered the sets of sports equipment for the events from $1$ to $N$. A combination of equipment can be used to hold a sports event $G$.

A sports event $G$ must satisfy the following conditions.

• A sports event $G$ must use at least two pieces of equipment with different numbers.
• For any two distinct pieces of equipment used in sports event $G$, the greatest common divisor of their numbers must be $K$.

Now I need to make a sports festival plan $P$ consisting of several sports events $G$. The conditions this plan $P$ has to satisfy are giving me a headache, so let me write them down.

• Sports festival plan $P$ cannot contain two or more sports events that use the same combination of equipment.
• For any sports event $G$ included in plan $P$, suppose there exists at least one valid sports event using more pieces of equipment than $G$, and let the list of all such events be $G'_1$, , , . Plan must contain at least one sports event that uses every piece of equipment used in .

Consider a sports festival plan $P$ containing as many sports events $G$ as possible. How many sports events $G$ would such a plan $P$ contain...? Noa did give me this task, but... Doesn't this sound more like an algorithm problem than an equipment management plan for the Kivotos Halo Festival? Wait! Noa! Where did you go!?

There is no sports event using more pieces of equipment than $G_4$, so $G_4$ can be included in plan $P$.

The sports event $G_4$ uses more pieces of equipment than each of $G_1, G_2, G_3$.

Since $G_1 \subset G_4, G_2 \subset G_4, G_3 \subset G_4$, the events $G_1, G_2, G_3$ can be included in plan $P$.

Therefore, plan $P$ contains $4$ sports events.

Time limit

1000 ms

Memory limit

1024 MB

Checker

CUSTOM