## ABA12A - Help Balaji!

no tags

Balaji was reading number theory. When reading about primes, he was thinking about numbers which could be expressed as a product of primes. He wanted to know the largest number in a range which could be expressed as a product of primes. Balaji’s maths teacher is not so good at maths and so he was taught that 1 is prime. You, being a good programmer, help him with the task.

### Input

The first line of input consists of C, the number of test cases, followed by C lines containing two space separated numbers a and b, the first and last number in the range (inclusive).

1 < C < 100

0 < A < B < 1e12

0 < B - A < 1e6

### Output

For each test case, print a single line containing the largest number which can be represented as a product of primes, considering 1 to be prime.

### Example

```Input:
1
1 4

Output:
4```

### Explanation of Test Case

4 can be expressed as 2 × 2.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>

using namespace std;

int main(){
int c;
scanf("%d",&c);
while(c--){
unsigned long long int a,b;
scanf("%llu%llu",&a,&b);
printf("%llu\n",b);
}
return 0;
}``````
Copy The Code &

Input

cmd
1
1 4

Output

cmd
4