Find the conflicting pair of tests with a black-box runner

A black-box run(tests) runs a set of tests together and reports failure when the set contains a conflicting pair of tests; any test alone passes. Find the conflicting pair with as few calls as possible. Follow-up: there may be several bad pairs; find all of them and analyse the number of calls.