CF776B Sherlock and his girlfriend

Sherlock has a new girlfriend (so unlike him!). Valentine's day is coming and he wants to gift her some jewelry. He bought $ n $ pieces of jewelry. The $ i $ -th piece has price equal to $ i+1 $ , that is, the prices of the jewelry are $ 2,3,4,...\ n+1 $ . Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don't have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used. Help Sherlock complete this trivial task.

N/A

N/A

In the first input, the colors for first, second and third pieces of jewelry having respective prices $ 2 $ , $ 3 $ and $ 4 $ are $ 1 $ , $ 1 $ and $ 2 $ respectively. In this case, as $ 2 $ is a prime divisor of $ 4 $ , colors of jewelry having prices $ 2 $ and $ 4 $ must be distinct.