% !TeX program=lualatex

\documentclass[12pt]{article}
\usepackage[table]{xcolor}
\usepackage{array}
\input{structure.tex}
\fancyhead[R]{
	\begin{minipage}{\textwidth}
		\raggedleft
		\includegraphics[width=2cm]{./logo2.png}
	\end{minipage}
}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}
	
\renewcommand{\tl}{$1$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача T72. ЛАМПИ}
\addauthor{Автор: Иван Лупов}{2026}{08}{28}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	КОНТРОЛНО СЪСТЕЗАНИЕ\\
	Габрово, 28 август 2026 г.\\
	7 клас
}
В стаята на Мария има $n$ светнати лампи, които е номерирала с числата от $1$ до $n$. За нея домашните са свършили, заради това тя играе следната игра с лампите си:

За всяко число $x = 1, 2, \dots, n$, всички лампи, които имат номера, делящи се на $x$, сменят състоянието си -- светнатите лампи стават изгасени, а изгасените стават светнати.

За да освети стаята си, Мария е решила, че са нужни поне $k$ светнати лампи. Вашата задача е да напишете програма \textbf{\texttt{lamps}}, която намира минималното $n$, такова че след като Мария извърши играта си, тя да е оставила светнати поне $k$ лампи.

\subsection{Вход}
Всеки тест се състои от $t$ на брой тестови случаи. За всеки тестов случай въвеждате единствено число $k$ -- минималния брой светнати лампи, които са необходими.

\subsection{Изход}
За всеки тестов случай да се изведе по едно число на отделен ред, което е търсеното минимално $n$.

\subsection{Ограничения}
\begin{itemize}
	\item $1 \le t \le 10^5$
	\item $1 \le k \le 10^{18}$ за всеки тестов случай
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & $k$ & $t$\\
		\hline
		$1$ & $20$ & $\leq 10^4$ & \SetCell[r=3]{}{$=1$} \\ 
		\hline
		$2$ & $20$ & $\leq 5 \times 10^5$ & \\ 
		\hline
		$3$ & $20$ & $\leq 10^{12}$ & \\ 
		\hline
		$4$ & $40$ & $\leq 10^{18}$ & $\leq 10^5$ \\ 
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
\end{table}

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение} \\
		\hline
		\texttt{\makecell[lt]{3\\1\\3\\8}}
		& 
		\texttt{\makecell[lt]{2\\5\\11}}
		& {Ще разиграем случая, в който трябва да оставим поне $3$ светнати лампи. Жълтите клетки са светнатите лампи, а белите -- изгасени. \\
			\vspace{0.2em}
			\begin{tabular}{|c|c|c|c|c|c|}
				\hline
				В началото & \cellcolor{yellow}$*$ & \cellcolor{yellow}$*$ & \cellcolor{yellow}$*$ & \cellcolor{yellow}$*$ & \cellcolor{yellow}$*$ \\ 
				\hline
				След $x=1$ & \cellcolor{white}$*$ & \cellcolor{white}$*$ & \cellcolor{white}$*$ & \cellcolor{white}$*$ & \cellcolor{white}$*$ \\ 
				\hline
				След $x=2$ & \cellcolor{white}$*$ & \cellcolor{yellow}$*$ & \cellcolor{white}$*$ & \cellcolor{yellow}$*$ & \cellcolor{white}$*$ \\ 
				\hline
				След $x=3$ & \cellcolor{white}$*$ & \cellcolor{yellow}$*$ & \cellcolor{yellow}$*$ & \cellcolor{yellow}$*$ & \cellcolor{white}$*$ \\ 
				\hline
				След $x=4$ & \cellcolor{white}$*$ & \cellcolor{yellow}$*$ & \cellcolor{yellow}$*$ & \cellcolor{white}$*$ & \cellcolor{white}$*$ \\ 
				\hline
				След $x=5$ & \cellcolor{white}$*$ & \cellcolor{yellow}$*$ & \cellcolor{yellow}$*$ & \cellcolor{white}$*$ & \cellcolor{yellow}$*$ \\ 
				\hline
			\end{tabular} \\
			\vspace{0.2em}
			Може да се докаже, че ако имаме по-малко от $5$ лампи, не можем да получим $3$ светнати след края на играта.
		}
		\\
		\hline
	\end{tblr}
\end{table}

\end{document}
