Not a full answer but perhaps a useful hint. If it is really the first item you want*, then
next(iter(q))
is much faster than
list(q)[0]
for large dicts, since the whole thing doesn't have to be stored in memory.
For 10.000.000 items I found it to be almost 40.000 times faster.
*The first item in case of a dict being just a pseudo-random item before Python 3.6 (after that it's ordered in the standard implementation, although it's not advised to rely on it).