Need help with random phone number generator

Ok so the project says to "Write an application that creates and prints a random phone number of the form XXX-XXX-XXXX. Include the dashes in the output. Do not let the first three digits contain an 8 or 9 (but don't be more restrictive than that), and make sure that the second set of three digits is not greater than 742. Hint: Think through the easiest way to construct the phone number. Each digit does not have to be determined separately."

So the problem I run into in trying to not determine each digit separately is that zeros will not appear before a number for example if it picks 95 as a random number it prints 95 and I want it to be printed 095. I also tried replacing spaces in a printf statement with 0's and i could not get that to work.

Did some looking around at other forums and it seems like this would be very hard with my limited knowledge in java so far and realized that my first three digits could have 8s and 9s in it. I am guessing i will be solving this by doing each digit separately for now but if there is a simpler solution that anyone has to offer that would be awesome

Any help would be very appreciated :)-:

Program as it stands right now:

package programmingProjects8_13;

//Programming Project 2.13

import java.util.Random;

public class PhoneNumbers {

public static void main(String[] args) {
Random rand = new Random();
int num1, num2, num3;

num1 = rand.nextInt(778);
num2 = rand.nextInt(743);
num3 = rand.nextInt(10000);

System.out.println("Random phone number "+num1+"-"+num2+"-"+num3);

}

}