問題 E1 とは制約のみが異なります

問題文

E1 - Make K [Easy] と同じ状況を考えます

次の制約下で問題を解いてください．

• $1 \leq T \leq \bold{10^5}$
• $2 \leq K_t \leq \bold{2 \times 10^6} \hspace{0.3em} \scriptsize (1 \leq t \leq T)$
• 入力はすべて整数である

サンプル

E1 と同一のものです．

3
3
7
60

2
4
8