Compact set of 3-valued test vectors for random pattern resistant faults are covered in multiple test passes. During a pass, its associated test cube specifies certain bits in the scan chain to be held fixed and others to change pseudo -randomly. We propose an algorithm to find a small number of cubes to cover all the test vectors, thus minimizing total test length. The test-cube finding algorithm repeatedly evaluates small perturbations of the current solution so as to maximize the expected test coverage of the cube. Experimental results show that our algorithm covers the test vectors by test cubes that are one to two orders of magnitude smaller in number with a much smaller increase in the percentage of specified bits. It outperforms comparable schemes reported in the literature.