#P3034. Heaven Cow与God Bull

    ID: 2165 传统题 1000ms 512MiB 尝试: 161 已通过: 52 难度: 5 上传者: 标签>CF1800普及+/提高-欧拉函数支配关系埃氏筛高精度乘法查询排序Poetize3

Heaven Cow与God Bull

题目描述

__int64 ago,there's a heaven cow called sjy...

A god bull named wzc fell in love with her...

As an OI & MOer,wzc gave sjy a quesiton...

给定一个整数 n n ,求一个整数 m m ,满足 m≤n m\leq n ,并且 mφ(m) \dfrac{m}{\varphi(m)} 的值最大。

注: φ(m) \varphi(m) 代表 m m 的欧拉函数,即不大于 m m 且与 m m 互质的数的个数。

输入格式

第一行是一个整数 T T ,表示该测试点有 T T 组数据。 接下来 T T 行,每行一个整数 n n ,意义如上所述。

输出格式

输出一共 T T 行,每行一个整数 m m 。

若对于某个 n n ,有不止一个满足条件的 m m ,则输出最小的 m m 。

样例输入

1
10

样例输出

6

数据规模与约定

对于 100%100\% 的数据,T≤100 T\leq 100 ,n≤1025000 n\leq 10^{25000} 。

题目来源

Poetize3