\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}

\renewcommand{\tl}{$0.4$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача D22. УНИТАРНИ ДЕЛИТЕЛИ}
\addauthor{Автори: Димитър Шапатов, Кирил Зашев}{2026}{03}{16}
\renewcommand{\header}{
	XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
	НАЦИОНАЛЕН КРЪГ\\
	Варна, 13 -- 16 март 2026 г.\\
	Група D, 6 клас\\
	\bigskip
}


Делител $d$ на естествено число $n$ наричаме \emph{унитарен}, ако е изпълнено условието $\gcd(d, \frac{n}{d})=1$. С $\gcd$ отбелязваме най-голям общ делител.

Напишете програма \textbf{\texttt{divs}}, която намира броя на унитарните делители на число $n$, за $q$ стойности на $n$.

\subsection{Вход}
От първия ред на стандартния вход се въвежда естественото число $q$ -- броят заявки. От следващия ред се въвеждат $q$ числа -- $i$-тото число е стойността на $n$ за $i$-тата заявка.

\subsection{Изход}
На един ред от стандартния изход се извежда търсеният брой за всяка заявка.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq q \leq 10^6$
	\item $1 \leq n \leq 10^6$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \makecell{\textbf{Необходими}\\ \textbf{подзадачи}} & $n$ & $q$ & \makecell{\textbf{Допълнителни}\\ \textbf{ограничения}} \\
		\hline
		$0$ &  $0$ &   $-$ & $-$ & $-$ & Примерният тест. \\ 
		\hline
		$1$ & $20$ &   $0$ & $\leq 10^4$ & $\leq 10^4$ & Няма. \\ 
		\hline
		$2$ & $20$ & $0-1$ & $\leq 10^5$ & $\leq 10^5$ & Няма. \\ 
		\hline
		$3$ & $20$ & $0-2$ & $\leq 5 \cdot 10^5$ & $\leq 5 \cdot 10^5$ & Няма. \\ 
		\hline
		$4$ & $20$ & $0-3$ & $\leq 5 \cdot 10^5$ & $\leq 10^6$ & Няма.  \\ 
		\hline
		$5$ & $20$ & $0-4$ & $\leq 10^6$ & $\leq 10^6$ & Няма. \\ 
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
\end{table}

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|X|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{\makecell[lt]{3 \\
		4 3 200}}
		& 
		\texttt{\makecell[lt]{2 2 4}}
		&
		Унитарните делители на $4$ са $1$ и $4$, на $3$ са $1$ и $3$, а на $200$ са $1, 8, 25$ и $200$. \\
		\hline
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}
