Blood Letter Process

Consider the process of an x blood letter which can be modeled by a function \(f(x)\). Initially, you are given the fraction \(\frac{0}{x}\). You repeatedly perform the following two steps until the fraction equals \(1\):

• Increase the numerator by \(1\).
• If the resulting fraction is reducible, reduce it to its simplest form.

The total number of operations performed is defined as \(f(x)\). You are given \(T\) test cases. In each case you are given a positive integer \(n\). For each test case, find the maximum value of \(f(x)\) for \(1 \le x \le n\).

Observation: For any prime \(x\), since \(\gcd(k,x)=1\) for all \(1 \le k < x\), the fraction will never be reduced until it becomes \(\frac{x}{x}\). Hence, \(f(x)=x\) when \(x\) is prime. For composite \(x\), reductions may occur and \(f(x)\) will be less than \(x\). Therefore, the answer for each test case is the largest prime number \(p\) such that \(p \le n\) (with the special case that when \(n=1\), we define \(f(1)=1\)).

inputFormat

The first line contains a single integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains one integer \(n\) (\(1 \le n \le N\)) indicating a test case.

outputFormat

For each test case, output a single line containing the maximum number of operations \(f(x)\) for \(1 \le x \le n\), which is equal to the largest prime \(p\) such that \(p \le n\) (with \(f(1)=1\)).

sample

1
1

1