It has taken anywhere from 1 to 70 fates for me to get them. I have 3 so far, but it is possible that it drops on the first FATE you do. It is just a low percentage to drop so in theory if you are VERY unlucky it could take hundreds.