Телефонски именик ради у телефону аутоматски кориснику нуди бројеве телефона који садрже тренутно унете цифре као подниз. Претпоставићемо да се у именику сваки број појављује највише једном и да су сви бројеви телефона деветоцифрени. Претпоставимо и да се, на пример, у именику тренутно налазе бројеви 123456789, 102030000 и 987123456.

• Када се унесе 123, кориснику се нуде бројеви 123456789 и 987123456.
• Када се унесе 30, кориснику се нуди само број 102030000.

Напиши програм који за сваки број у именику одређује најкраћи низ цифара које је могуће откуцати да би се приказао само тај број (ако има више таквих низова, приказати онај који се први јавља у броју, гледајући слева надесно).

Улаз

Са стандардног улаза се учитава број телефонских бројева у именику \(n\) (\(1 \leq n \leq 10^5\)), а затим \(n\) деветоцифрених бројева из \(n\) наредних редова.

Излаз

На стандардни излаз исписати \(n\) бројева који за сваки унети број редом дају минимални број цифара.

Пример 1

Улаз

3
123456789
102030000
987123456

Излаз

67
0
98

Пример 2

Улаз

4
123456789
193456789
134567819
934567891

Излаз

2
193
13
91