from collections import Counter
from itertools import combinations_with_replacement
from sys import exit
people, dishes = None, None
memo = None
def done(state):
for i in range(dishes+1):
for j in range(i):
if state[i] == state[j]:
return False
return True
def solve(state):
X, Y = state
if len(X) == dishes: return 0
if state in memo: return memo[state]
old_class = []
for i,j in enumerate( list(X)+[Y] ): old_class += [i]*j
answer = 123456789
for order in combinations_with_replacement( range(dishes), people ):
new_class_sizes = Counter()
for d in range(dishes+1):
new_class_sizes[ ( old_class[d], order.count(d) ) ] += 1
new_Y = new_class_sizes[ (old_class[dishes], order.count(dishes)) ]
new_X = list(new_class_sizes.values())
new_X.remove( new_Y )
new_X.sort()
if len(X) == len(new_X): continue # no progress has been made
new_state = ( tuple(new_X), new_Y )
answer = min( answer, 1 + solve(new_state) )
memo[state] = answer
return answer
T = int( input() )
for test in range(T):
input()
people, dishes = [ int(x) for x in input().split() ]
memo = {}
print( solve( ( tuple(), dishes+1 ) ) )