One quick remark: the upper bound will be $$ O\left(\min_j \frac{1}{H^2(p_j,q_j)}\right) $$ where $H$ is the Hellinger distance, not TV (we have $H^2\lesssim TV \lesssim H$). The sample complexity of simple hypothesis testing is captured by Hellinger, not total variation.
I suspect this is tight on an instance-per-instance basis as well, but don't have a proof. Rather, I don't have a proof for adaptive algorithms (those which can choose which $i$ to query, based on previously received samples): for non-adaptive algorithms (which choose ahead of time how many samples to ask from each $i$), then I believe I can prove the lower bound, using elementary properties of Hellinger distance.