Se dă un șir de n fracții. Fiecare fracție este dată printr-o pereche de numere reprezentând numărătorul și numitorul fracției. De exemplu 2010 34 reprezintă fracția $2010 \over 34$ . O fracție poate fi ireductibilă sau se poate.

Cerința

Să se afișeze, pentru fiecare fracție:

1) Prin câte moduri distincte se poate simplifica.
2) Fracția ireductibilă.

Date de intrare

În fișierul de intrare fractii4.in pe prima linie se găsesc numerele P și n, iar pe următoarele n linii se găsesc n perechi de numere, reprezentând numărătorul și numitorul fiecărei fracții, separate printr-un spațiu.

Date de ieșire

Pe fiecare din cele n linii ale fișierului fractii4.out se găsesc, pentru fiecare fracție, în ordinea dată în fișierul de intrare:

1) Dacă P = 1, numărul de simplificări distincte posibile. Dacă nu este posibilă nicio simplificare (fracția este ireductibilă) se va afișa -1.
2) Dacă P = 2, fracția ireductibilă, numărătorul și numitorul fiind separați prin /.

Restricții și precizări

• n <= 100 000
• 0 < numitor, numărător < 2 000 000
• P este 1 sau 2

Exemplul 1

fractii4.in

1 4
8 4
3 2
1 6
12 6

fractii4.out

2
-1
-1
3

Explicație

Pentru acest test P = 1, deci se va rezolva doar cerinţa 1).
Prima fracție se poate simplifica prin 2 moduri: prin 2 și 4.
A doua este ireductibilă, deci se va afișa -1.
A treia este ireductibilă, deci se va afișa -1.
A patra se poate simplifica prin 3 moduri: 2, 3 și 6.

Exemplul 2

fractii4.in

2 3
22 6
11 4
125 25

fractii4.out

11/3
11/4
5/1

Explicație

Pentru acest test P = 2, deci se va rezolva doar cerinţa 2).
Prima fracție se simplifică prin 2.
A doua fracție este ireductibilă, deci va fi afișată fără schimbare.
Ultima fracție poate fi redusă prin 25 și devine ireductibilă. Chiar dacă
numitorul este 1, acesta va fi afișat.

#include <bits/stdc++.h>
using namespace std;
ifstream fin("fractii4.in");
ofstream fout("fractii4.out");
int prim(int n)
{
    if(n==0 || n==1) return 0;
    if(n==2) return 1;
    if(n%2==0) return 0;
    else for(int i=3;i*i<n;i++)
    {
        if(n%i==0) return 0;
    }
    return 1;
}
int prime(int a, int b)
{
    int d,r;
    if(b==0) d=a;
    else while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    d=a;
    if(d==1) return 1;
    else return 0;
}
int main()
{
    int n,a,b,p;
    fin>>p>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a>>b;
        int x=a,y=b,r,q;
        if(p==1)
        {
         if(prime (a,b)) fout<<"-1"<<endl;
         else
        {
         int d=0,d1,cate=1,p=0;
         while(b!=0)
        {
            r=a%b;
            a=b;
            b=r;
        }
        d1=a;
        for(int j=1;j*j<=d1;j++)
    {
        if(d1%j==0) d=d+2;
        if(j*j==d1) d--;
    }
        fout<<d-1<<endl;
        }
        }
        else
            if(p==2)
        {
            int t;
            while(b!=0)
        {
            r=a%b;
            a=b;
            b=r;
        }
        t=a;
            fout<<x/t<<"/"<<y/t<<endl;
        }
    }
return 0;
}