1. a **new pair of** shoes / pants / scissors
2. a **pair of new** shoes / pants / scissors

I can’t find which one of those two it should be, and I’ve seen some debate about it. 

“A new pair of shoes”: Could it imply that the shoes previously were part of a different pair? 

But on the other hand, if it’s a pair of shoes, why would one have to state that both shoes are new when saying *a pair of new shoes*?

Which is correct, or doesn’t it matter?