[phreenet]

First attempt I tried:

  45677
  56779 (Didn't read the instructions, the 5 should have stayed from 1st)
  15809
  35869
  65839 (Solved)

EDIT: I'm slow today, just realized they are both the same primes.