#P11398. 神牛的问题

    ID: 10338 传统题 2000ms 256MiB 尝试: 4 已通过: 3 难度: 9 上传者: 标签>CF2600省选/NOI-欧拉函数埃氏筛试除法分解质因数阈值划分大小情况暴力枚举深度优先搜索试除法判素数极端元素优先处理约数相关

神牛的问题

题目描述

数论大神 ydzr 正在研究数论。他得到了一个如下的函数:

f(n)=∑i=1n[gcd⁡(i,n)=1]×if(n)=\sum_{i=1}^n[\gcd(i,n)=1]\times i

作为一位神牛,他自然很快地想出了如何计算这个函数。于是他开始思考对于一个给定的 xx,如何找到一个最小的正整数 nn 使得 f(n)=xf(n)=x。这也当然难不倒他。于是他把这个问题交给了你,想检验你的数论水平。由于只回答一个问题无法展现你的水平,他将会问你 TT 次。

输入格式

第一行一个数,表示 TT。

后面 TT 行,每行一个正整数,表示 xx。

输出格式

输出 TT 行,每行一个整数,如果存在解则输出最小的 nn,否则输出 −1-1。

样例

4
20
21
1
7
10
7
1
-1

数据范围

子任务编号 T≤T\leq x≤x\leq 分值
1 10410^4 10910^9 1010
2 100100 101210^{12} 3030
3 101810^{18}
4 10410^4 2×10182\times 10^{18}