# The product mystery - Codechef

### Problem Statement :

```Given two positive numbers B and C, what is the minimum positive value of A, such that A⋅B is divisible by C.

Here, A⋅B denotes the value obtained when A is multiplied by B.

Input Format

The first line will contain an integer T - number of test cases. Then the test cases follow.
The first and only line of each test case contains two integers B and C.

Output Format

For each test case, output the minimum value of A such that A⋅B is divisible by C.

Constraints

1≤T≤105
1≤B,C≤109

Sample Input 1

2
2 4
8 12

Sample Output 1
2
3```

### Solution :

```                        ```Solution in C++ :

#include<bits/stdc++.h>
#include <iterator>
#include <iostream>
#include <numeric>
#include <math.h>
#define ll long long
#define ull long
#define mpa make_pair
#define pb push_back
#define ff first
#define pii pair<ll,ll>
#define dd long double
#define trace(x) cerr << #x << " : " << x << endl
#define ss second
#define boost ios_base::sync_with_stdio(0)
#define forp(i,a,b) for(ll i=a;i<=b;i++)
#define rep(i,n)    for(ll i=0;i<n;++i)
#define ren(i,n)    for(ll i=n-1;i>=0;i--)
#define forn(i,a,b) for(ll i=a;i>=b;i--)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end();
#define sc(x) scanf("%lld",&x)
#define clr(x,val) memset(x,val,sizeof(x))
#define pr(x) printf("%lld\n",x)
#define gc getchar
#define pdd pair<dd,dd>
#define prec(x) cout<<fixed<<setprecision(x)
#define fre freopen("input.txt","r",stdin),freopen("output.txt","w",stdout)
#define arr array
using namespace std;
ll a;
void solve(ll tc){
ll b,c;
cin>>b>>c;
ll gc=__gcd(b,c);
cout<<c/gc<<endl;

}

int main(){
boost;

//pre_cum();
//prec(20);
//fre;

ll t=1;
ll tc=1;
cin>>t;

while(t--){
solve(tc);
tc++;
}

return 0;

}```
```

```                        ```Solution in Java :

import java.util.*;
import java.io.*;

public class Main {

static long startTime = System.currentTimeMillis();

// for global initializations and methods starts here

// global initialisations and methods end here

static void run() {
boolean tc = true;

try (OutputStream out = new BufferedOutputStream(System.out)) {

//long startTime = System.currentTimeMillis();

int testcases = tc ? r.ni() : 1;
int tcCounter = 1;
// Hold Here Sparky------------------->>>
// Solution Starts Here

start:
while (testcases-- > 0) {

// a*b = c

long b = r.nl();
long c = r.nl();

out.write((c / gcd(b, c) + " ").getBytes());
out.write(("\n").getBytes());
}
// Solution Ends Here
} catch (IOException e) {
e.printStackTrace();
}
}

final private int BUFFER_SIZE = 1 << 16;
private final DataInputStream din;
private final byte[] buffer;
public StringTokenizer st;

din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
}

public AdityaFastIO(String file_name) throws IOException {
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
}

public String word() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

public String line() {
String str = "";
try {
} catch (IOException e) {
e.printStackTrace();
}
return str;
}

public String readLine() throws IOException {
byte[] buf = new byte; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n') break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}

public int ni() throws IOException {
int ret = 0;
while (c <= ' ') c = read();
boolean neg = (c == '-');
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (neg) return -ret;
return ret;
}

public long nl() throws IOException {
long ret = 0;
while (c <= ' ') c = read();
boolean neg = (c == '-');
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (neg) return -ret;
return ret;
}

public double nd() throws IOException {
double ret = 0, div = 1;
while (c <= ' ') c = read();
boolean neg = (c == '-');
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
if (neg) return -ret;
return ret;
}

private void fillBuffer() throws IOException {
if (bytesRead == -1) buffer = -1;
}

private byte read() throws IOException {
return buffer[bufferPointer++];
}

public void close() throws IOException {
if (din == null) return;
din.close();
}
}

public static void main(String[] args) throws Exception {
run();
}

int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = r.ni();
return arr;
}

long[] arr = new long[n];
for (int i = 0; i < n; i++) arr[i] = r.nl();
return arr;
}

List<Integer> al = new ArrayList<>();
for (int i = 0; i < n; i++) al.add(r.ni());
return al;
}

List<Long> al = new ArrayList<>();
for (int i = 0; i < n; i++) al.add(r.nl());
return al;
}

static long mod = 998244353;

static long modInv(long base, long e) {
long result = 1;
base %= mod;
while (e > 0) {
if ((e & 1) > 0) result = result * base % mod;
base = base * base % mod;
e >>= 1;
}
return result;
}

StringTokenizer st;

}

String word() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

String line() {
String str = "";
try {
} catch (IOException e) {
e.printStackTrace();
}
return str;
}

int ni() {
return Integer.parseInt(word());
}

long nl() {
return Long.parseLong(word());
}

double nd() {
return Double.parseDouble(word());
}
}

static int MOD = (int) (1e9 + 7);

static long powerLL(long x, long n) {
long result = 1;
while (n > 0) {
if (n % 2 == 1) result = result * x % MOD;
n = n / 2;
x = x * x % MOD;
}
return result;
}

static long powerStrings(int i1, int i2) {
String sa = String.valueOf(i1);
String sb = String.valueOf(i2);
long a = 0, b = 0;
for (int i = 0; i < sa.length(); i++) a = (a * 10 + (sa.charAt(i) - '0')) % MOD;
for (int i = 0; i < sb.length(); i++) b = (b * 10 + (sb.charAt(i) - '0')) % (MOD - 1);
return powerLL(a, b);
}

static long gcd(long a, long b) {
if (a == 0) return b;
else return gcd(b % a, a);
}

static long lcm(long a, long b) {
return (a * b) / gcd(a, b);
}

static long lower_bound(int[] arr, int x) {
int l = -1, r = arr.length;
while (l + 1 < r) {
int m = (l + r) >>> 1;
if (arr[m] >= x) r = m;
else l = m;
}
return r;
}

static int upper_bound(int[] arr, int x) {
int l = -1, r = arr.length;
while (l + 1 < r) {
int m = (l + r) >>> 1;
if (arr[m] <= x) l = m;
else r = m;
}
return l + 1;
}

static void addEdge(ArrayList<ArrayList<Integer>> graph, int edge1, int edge2) {
}

public static class Pair implements Comparable<Pair> {
int first;
int second;

public Pair(int first, int second) {
this.first = first;
this.second = second;
}

public String toString() {
return "(" + first + "," + second + ")";
}

public int compareTo(Pair o) {
// TODO Auto-generated method stub
if (this.first != o.first)
return (int) (this.first - o.first);
else return (int) (this.second - o.second);
}
}

public static class PairC<X, Y> implements Comparable<PairC> {
X first;
Y second;

public PairC(X first, Y second) {
this.first = first;
this.second = second;
}

public String toString() {
return "(" + first + "," + second + ")";
}

public int compareTo(PairC o) {
// TODO Auto-generated method stub
return o.compareTo((PairC) first);
}
}

static boolean isCollectionsSorted(List<Long> list) {
if (list.size() == 0 || list.size() == 1) return true;
for (int i = 1; i < list.size(); i++) if (list.get(i) <= list.get(i - 1)) return false;
return true;
}

static boolean isCollectionsSortedReverseOrder(List<Long> list) {
if (list.size() == 0 || list.size() == 1) return true;
for (int i = 1; i < list.size(); i++) if (list.get(i) >= list.get(i - 1)) return false;
return true;
}

}```
```

```                        ```Solution in Python :

import math
for _ in range(int(input())):
b, c = map(int, input().split())
print(c // math.gcd(b, c))```
```

## Cube Summation

You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x y z W updates the value of block (x,y,z) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coor

## Direct Connections

Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do

## Subsequence Weighting

A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =