If is even, is nonabelian of order .
If is odd, perhaps we can decompose into a product of prime powers and show that for every odd prime there exists a nonabelian group of order ...
So, a non-abelian group of order ? Does the group with presentation work? Clearly it is non-abelian (as if it was ), and it has order (as with a minimal generating set and ).
(This is a specific case of the group , , the only non-abelian p-group that has a cyclic maximal subgroup and is not of maximal class - see Robinson, A Course in the Theory of Groups, section 5.3.4)