1 of 3

Jelly, 12 bytes

Dd4d2FṙRḄṢIS

Too slow and memory hungry for the last two test cases. This could be fixed, at the cost of a byte, by replacing ṙR with ṙJ$.

Try it online!