401605: GYM100499 D Pairwise Coprime Set

Two positive numbers are called coprime (or relatively prime) if their greatest common divisor is 1. A set of integers is said to be pairwise coprime if for every pair of different element (a, b), a and b are co-prime.

Given set S of N first positive integers, your task is to find the largest subset S' of S such that S' is pairwise coprime.

The first line of input is the number T - the number of tests (T ≤ 1000). Then T tests follow. Each test will be printed in one line with the number N. (1 ≤ N ≤ 10⁶)

For each test, print Case#i: p where i is the 1-based index of the test and p is the size of the largest subset.

1
5

Case #1: 4

{1, 2, 3, 5} and {1, 3, 4, 5} are the largest pairwise coprime subset.