# Server Cluster Size
## Problem Statement
You are given an array $a$ of $n$ positive integers, where $a_i$ represents a property of the $i$-th server ($0$-indexed). A network of servers is formed based on these properties.
Two distinct servers at indices $i$ and $j$ are considered **connected** if the greatest common divisor (${GCD}$) of their properties, $a_i$ and $a_j$, is greater than $1$. That is, if ${GCD}(a_i, a_j) > 1$. This connectivity relation is transitive: if server $A$ is connected to server $B$, and server $B$ is connected to server $C$, then server $A$ is also considered connected to server $C$. This forms connected components, which we refer to as **clusters**.
Your task is to determine the size of the cluster to which each server belongs. You should return an array of $n$ integers, where the $k$-th value in the array ($0$-indexed) is the total number of servers in the cluster containing server $k$.
## Input Format
- The first line contains a single integer $n$ ($1 \le n \le 10^5$), representing the number of servers.
- The second line contains $n$ space-separated integers $a_0, a_1, \ldots, a_{n-1}$ ($1 \le a_i \le 10^5$), representing the properties of the servers.
## Output Format
Print $n$ space-separated integers. The $k$-th integer should be the size of the cluster to which server $k$ belongs.
## Sample Test Cases
### Sample Input 1
```
3
3 3 3
```
### Sample Output 1
```
3 3 3
```
### Sample Input 2
```
5
2 3 6 1 5
```
### Sample Output 2
```
3 3 3 1 1
```
## Constraints
- $1 \le n \le 10^5$
- $1 \le a_i \le 10^5$
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
### Sample 1:
Given $n=3$ and $a = [3, 3, 3]$.
- For servers $0$ and $1$: $\text{GCD}(a_0, a_1) = \text{GCD}(3, 3) = 3 > 1$. They are connected.
- For servers $0$ and $2$: $\text{GCD}(a_0, a_2) = \text{GCD}(3, 3) = 3 > 1$. They are connected.
- For servers $1$ and $2$: $\text{GCD}(a_1, a_2) = \text{GCD}(3, 3) = 3 > 1$. They are connected.
All servers are connected to each other, forming a single cluster of size $3$. Thus, each server belongs to a cluster of size $3$.
### Sample 2:
Given $n=5$ and $a = [2, 3, 6, 1, 5]$.
- Consider server $0$ ($a_0=2$):
- With server $1$ ($a_1=3$): $\text{GCD}(2, 3) = 1$. Not connected.
- With server $2$ ($a_2=6$): $\text{GCD}(2, 6) = 2 > 1$. Connected.
- With server $3$ ($a_3=1$): $\text{GCD}(2, 1) = 1$. Not connected.
- With server $4$ ($a_4=5$): $\text{GCD}(2, 5) = 1$. Not connected.
- Consider server $1$ ($a_1=3$):
- With server $2$ ($a_2=6$): $\text{GCD}(3, 6) = 3 > 1$. Connected.
- (Already checked with server $0$)
- Server $2$ ($a_2=6$) is connected to server $0$ ($a_0=2$) and server $1$ ($a_1=3$).
Servers $0, 1, 2$ form a cluster because $0$ is connected to $2$, and $1$ is connected to $2$. By transitivity, they are all in the same cluster. The size of this cluster is $3$.
- Server $3$ ($a_3=1$):
- $\text{GCD}(1, x) = 1$ for any $x$. So, server $3$ is not connected to any other server. It forms a cluster of size $1$.
- Server $4$ ($a_4=5$):
- Not connected to $0, 1, 2, 3$. It forms a cluster of size $1$.
The cluster sizes for servers $0, 1, 2, 3, 4$ are $3, 3, 3, 1, 1$ respectively.
Loading problem statement...