package main

import . "fmt"

func main() {
	var t int
	Scan(&t)
	for ; t > 0; t-- {
		var n,k,x int
		Scan(&n,&k)
		// 素数の間隔とやらは10^9以下なら300以下らしい？
		for x = n; x > 1 && x > n-300; x-- {
			ok := true
			for a:=1; a*a<=x&&a<=k; a++ {
				if x%a==0&&x/a<=k {
					ok = false
					break
				}
			}
			if ok {
				Println(x)
				x = -1
				break
			}
		}
		if x > 0 {
			Println(-1)
		}
	}
	
}