The problem is basically harder for larger \(N\), so let us think of a way to make \(N\) larger.

◆Basic Strategy

If a set \(A = \{a_1,\ldots,a_n\}\) satisfies the conditions, it will still satisfy them after we add a multiple of \(a_i\) to it.

For example, let us start with Sample Output 1: \(A = \{84, 60, 105, 70\}\). We can add multiples of \(84\) and multiples of \(60\) while still satisfying the conditions. After making as many additions as possible, we can achieve \(N = 429\): the set of all numbers that are multiples of \(84\), \(60\), \(105\), or \(70\).

◆Our Solutions

Starting with \(A = \{84,60,105,70\}\) achieved \(N = 429\). We can make a better choice of \(A\) at the beginning to achieve larger \(N\).

• Writer’s solution: the set of all numbers that are multiples of \(6\), \(10\), or \(15\) has \(2666\) elements and satisfies the conditions.
• Tester’s solution: the set of all numbers that are multiples of \(6\), \(10\), \(14\), \(22\), or \(1155\) has \(2926\) elements and satisfies the conditions.

We can solve the problem by printing a coprime subset of such a set.

【Sample Implementation】 https://atcoder.jp/contests/arc118/submissions/22269560 （Python, \(N \leq 2666\)）