Условие

---

Задача I. Делител
---
Казваме, че едно число A е по-добро от друго число B, ако сумата на цифрите на A е по-голяма от сумата на цифрите на B. Ако пък сумите от цифрите на двете числа са равни, то по-добро е числото, което е по-малко от другото. Естествено, ако A и B съвпадат, няма как да определим кое число е по-добро.

Напишете програма, която намира най-лошия делител на зададено число N. Смята се, че делители на числото са и, както числото 1, така и самото число. 

Вход
---
На първия ред е зададен броят на тестовите примери. Всеки от следващите редове съдържа едно цяло число N.

Изход
---
За всеки тестов пример се извежда един ред, съдържащ едно цяло число – намереният най-лош делител.

Ограничения
---
0 ≤ N ≤ 10^50

Примерен вход 
---
2
2325
75810

Примерен изход
---
1
10