#include <iostream>
using namespace std;
 long long  a,b,t,c,d,k,s,f;

int main ()
{
    c = 1; k = 0;
   cin >>t;
   for (t;t>=1;--t) {
     cin >>a;
      cin >>b;
   if ( b%a==0)
   {
       for( ; d != b; ++c )
       {
         d = a*c;
          if ( b % d == 0)
          {
              k= k+1;
              a = d;
              c = 1;
          }
       }
       cout << k<<"\n";
   }
   else
      cout << "0\n";
   c=1; k=0;
   }
    return 0;

}

Excuse me
but your algo is wrong.

input:
5
1 1000000000
1 1000000000
1 1000000000
2 10
2 10

your answer:
19
0
0
2
0

right anse:
19
19
19
2
2

Check it up!..
Press any key to continue . . .

thx