from math import modf from sys import stdin def main(): input = lambda: stdin.readline()[:-1] Q = int(input()) NK = [tuple(map(int, input().split())) for _ in [0] * Q] for n, k in NK: if k == 1: print(n - 1) else: m, d = modf(n ** (1 / k)) print(int(d + 1)) if m else print(int(d)) main()