# The two numbers solution codechef

## The two numbers solution codechef

Given two positive integers aa and bb, we define f(a,b)=lcm(a,b)gcd(a,b)f(a,b)=lcm(a,b)−gcd(a,b), where lcmlcm denotes the lowest common multiple and gcdgcd denotes the greatest common divisor.

Chef has a positive integer NN. He wonders, what is the maximum value of f(a,b)f(a,b) over all pairs (a,b)(a,b) such that aa and bb are positive integers, and a+b=Na+b=N?

## The two numbers solution codechef

• The first line of input will contain an integer TT — the number of test cases. The description of TT test cases follows.
• The first line of each test case contains an integer NN, as described in the problem statement.

### Output Format

For each test case, output the maximum value of f(a,b)f(a,b) that can be obtained while satisfying the conditions on aa and bb.

• 1T1051≤T≤105
• 2N1092≤N≤109

### Sample Input 1

3
3
4
6


## The two numbers solution codechef

1
2
4


### Explanation

Test case 11: There are two possible pairs of (a,b)(a,b)(1,2)(1,2) and (2,1)(2,1). For both of these pairs, we have lcm(a,b)=2lcm(a,b)=2 and gcd(a,b)=1gcd(a,b)=1, which gives f(a,b)=1f(a,b)=1.

Test case 22: For (1,3)(1,3), we have lcm(1,3)=3lcm(1,3)=3 and gcd(1,3)=1gcd(1,3)=1, giving f(1,3)=31=2f(1,3)=3−1=2. It can be shown that this is the maximum possible value of f(a,b)f(a,b) that can be obtained while satisfying the above conditions.

Test case 33: For (1,5)(1,5), we have lcm(1,5)=5lcm(1,5)=5 and gcd(1,5)=1gcd(1,5)=1, giving f(1,5)=51=4f(1,5)=5−1=4. It can be shown that this is the maximum possible value of f(a,b)f(a,b) that can be obtained while satisfying the above conditions.