Algorithm

A. Maximum GCD
time limit per test
1 second
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/1370/A
input
standard input
output
standard output

Let's consider all integers in the range from 11 to n� (inclusive).

Among all pairs of distinct integers in this range, find the maximum possible greatest common divisor of integers in pair. Formally, find the maximum value of gcd(a,b)gcd(�,�), where 1≤a<b≤n1≤�<�≤�.

The greatest common divisor, gcd(a,b)gcd(�,�), of two positive integers a� and b� is the biggest integer that is a divisor of both a� and b�.

Input

The first line contains a single integer t� (1≤t≤1001≤�≤100)  — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer n� (2≤n≤1062≤�≤106).

Output

For each test case, output the maximum value of gcd(a,b)gcd(�,�) among all 1≤a<b≤n1≤�<�≤�.

Example
input
Copy
2
3
5
output
Copy
1
2
Note

In the first test case, gcd(1,2)=gcd(2,3)=gcd(1,3)=1gcd(1,2)=gcd(2,3)=gcd(1,3)=1.

In the second test case, 22 is the maximum possible value, corresponding to gcd(2,4)gcd(2,4).

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

int main(){
  int t;
  cin>>t;
  int n;
  while(t--){
    cin>>n;
    if(n%2 != 0){
      n--;
      cout<<(n/2)<<endl;
      continue;
    }
    cout<<(n/2)<<endl;
  }
  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2
3
5

Output

x
–
+
cmd
1
2
Advertisements

Demonstration

Codeforcess solution 1370-A A. Maximum GCD ,C++, Java, Js and Python,1370-A,Codeforcess solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+