```go
package main

import "fmt"

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		var n, k int64
		fmt.Scan(&n, &k)
		if k >= n {
			fmt.Println(1)
			continue
		}
		var ans int64 = n
		found := false
		for j := int64(1); j*j <= n; j++ {
			if n%j == 0 {
				if n/j <= k {
					fmt.Println(j)
					found = true
					break
				}
				if j <= k {
					ans = n / j
				}
			}
		}
		if !found {
			fmt.Println(ans)
		}
	}
}
```