2020 年 “联想杯”全国高校程序设计在线邀请赛暨第三届上海理工大学程序设计竞赛

Setsuna has been fascinated by coprime pairs recently, so she decided to play a game about numbers.

Here are $n$ integers $a_1,a_2,\cdots ,a_n(2\le a_i\le {10}^{18})$. Setsuna wants to divide the numbers into as few groups as possible so that each number is exactly in one group and the numbers in each group are coprime with each other.

We say that positive integers $x$ and $y$ are coprime if and only if $gcd(x,y)=1$, where $gcd(x,y)$ refers to their greatest common divisor.

However, Setsuna is not good at math, so she only comes up with a fake algorithm.

Her greedy algorithm is obviously wrong, so we need to hack her solution.

You are given one integer $k$. You need to find the input consisting of $n(n\le 300)$ integers and a corresponding partition to the input(not necessarily be the minimum partition), which satisfies $X=Y+k$, where $Y$ is the number of groups of your partition and $X$ is the answer of her algorithm to your input.

It can be proved that the answer always exists.