import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
 
        for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
 
            int operations = 0;
            while (n % 2 == 0) {
                n /= 2;
                operations++;
            }
 
            int j = 3;
            while (j * j <= n) {
                while (n % j == 0) {
                    n /= j;
                    operations++;
                }
                j += 2;
            }
 
            if (n > 2) {
                operations++;
            }
 
            if (n == 1) {
                System.out.println(operations >= m ? operations : -1);
            } else {
                System.out.println(-1);
            }
        }
    }
}
 

aW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwoKcHVibGljIGNsYXNzIE1haW4gewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIFNjYW5uZXIgc2Nhbm5lciA9IG5ldyBTY2FubmVyKFN5c3RlbS5pbik7CiAgICAgICAgaW50IHQgPSBzY2FubmVyLm5leHRJbnQoKTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCB0OyBpKyspIHsKICAgICAgICAgICAgaW50IG4gPSBzY2FubmVyLm5leHRJbnQoKTsKICAgICAgICAgICAgaW50IG0gPSBzY2FubmVyLm5leHRJbnQoKTsKCiAgICAgICAgICAgIGludCBvcGVyYXRpb25zID0gMDsKICAgICAgICAgICAgd2hpbGUgKG4gJSAyID09IDApIHsKICAgICAgICAgICAgICAgIG4gLz0gMjsKICAgICAgICAgICAgICAgIG9wZXJhdGlvbnMrKzsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgaW50IGogPSAzOwogICAgICAgICAgICB3aGlsZSAoaiAqIGogPD0gbikgewogICAgICAgICAgICAgICAgd2hpbGUgKG4gJSBqID09IDApIHsKICAgICAgICAgICAgICAgICAgICBuIC89IGo7CiAgICAgICAgICAgICAgICAgICAgb3BlcmF0aW9ucysrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaiArPSAyOwogICAgICAgICAgICB9CgogICAgICAgICAgICBpZiAobiA+IDIpIHsKICAgICAgICAgICAgICAgIG9wZXJhdGlvbnMrKzsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgaWYgKG4gPT0gMSkgewogICAgICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKG9wZXJhdGlvbnMgPj0gbSA/IG9wZXJhdGlvbnMgOiAtMSk7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oLTEpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9Cg==

NAoxMCA1CjEgNQoxMCA0CjMgNAo=

4
10 5
1 5
10 4
3 4