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.