3483. Common Divisor

import java.io.*;

public class Main {

    /**
     * http://acm.tju.edu.cn/toj/showp3483.html
     * @author hunglee
     */
    public static void main(String[] args) throws IOException {
        
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(System.out);
        
        int t, n, m, a, i, j, k, res;
        in.nextToken();
        t = (int) in.nval;
        while (t-- > 0) {
            in.nextToken();
            n = (int) in.nval;
            in.nextToken();
            m = (int) in.nval;
            
            a = gcd(n, m);
            res = 1;
            k = 0;
            while (a % 2 == 0) {
                ++k;
                a = a >> 1;
            }
            res *= (k + 1);
            k = 0;
            while (a % 3 == 0) {
                ++k;
                a /= 3;
            }
            res *= (k + 1);
            i = 5; j = 2;
            while (a > 1 && i * i <= a)
                if (a % i == 0) {
                    k = 0;
                    while (a % i == 0) {
                        ++k;
                        a /= i;
                    }
                    res *= (k + 1);
                } else {
                    i += j;
                    j = 6 - j;
                }
            if (a > 1)
                res = res << 1;
            out.println(res);
        }
        out.flush();
    }
    private static int gcd(int a, int b) {
        int r;
        while (b != 0) {
            r = a % b; a = b; b = r;
        }
        return a;
    }

}