#P1897. 2024.8.17-MT-第1题-gcd

2024.8.17-MT-第1题-gcd

题目描述

小乖对 gcdgcd (最大公约数) 很感兴趣, 他会询问你tt次。 每次询问给出一个大于 11 的正整数 nn, 你是否找到一个数字m(2≤m≤n)m(2 ≤m ≤ n)，使得 gcd(n,m)gcd(n, m) 为素数.

注：原题为给出任意解，本题中请给出最小值作为答案

输入描述

每个测试文件将包含多组测试数据,每组测试数据的第一行包含一个整数 k(2≤k≤105)k (2 ≤ k ≤ 10^5), 表示有k k 个待测数字.接下来 kk 行,每行包含一个整数n(2≤n≤109) n (2 ≤ n ≤ 10^9),表示待测的数字.

输出描述

对于每一组测试数据, 在一行上输出一个整数，代表数字 mm。

示例 1

输入

2
114
15

输出

2
3

知识点:*****

查看知识点以及同类型题目

Statistics