```go
package main

import (
	"fmt"
)

func main() {
	var t int
	fmt.Scan(&t)
	for tc := 0; tc < t; tc++ {
		var x, n int
		fmt.Scan(&x, &n)
		limit := x / n
		ans := 1
		for i := 1; i*i <= x; i++ {
			if x%i == 0 {
				if i <= limit && i > ans {
					ans = i
				}
				other := x / i
				if other <= limit && other > ans {
					ans = other
				}
			}
		}
		fmt.Println(ans)
	}
}
```