#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
string s;
int a[100005];/**< a存储高精度 */
int test(int x)/**< 测试一下存在a数组的高精度数字能否被x整除 */
{
    int i,j,y=a[s.size()-1];
    for(i=s.size()-2; i>=0; i--)
        y=y%x*10+a[i];
    if(y%x==0)
        return 1;
    else
        return 0;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,t,sum;
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof(a));
        sum=0;
        cin>>s;
        for(i=0; i<s.size(); i++)
        {
            a[i]=s[s.size()-1-i]-'0';
            sum+=a[i];
        }
        int b[10],total=1;
        b[1]=sum;
        while(sum>=10)
        {
            int s=0;
            while(sum)
                s+=sum%10,sum/=10;
            sum=s;
            b[++total]=sum;
        }
        for(j=2;; j++)/**< 暴力检查满足条件的j，除了开始的n和第一次的sum外，其他数字都很小，因此考虑暴力枚举的方法 */
        {
            if(test(j)==1) /**< 能整除情况 */
            {
                for(i=1; i<=total; i++)
                {
                    if(b[i]%j!=0)
                        break;
                }
                if(i>total)
                {
                    cout<<j<<endl;
                    break;
                }
            }
            else/**< 不能整除情况 */
            {
                for(i=1; i<=total; i++)
                {
                    if(b[i]%j==0)
                        break;
                }
                if(i>total)
                {
                    cout<<j<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}