问题描述

百江在做质数类的题目的时候计算需要质数时把自己算崩溃了，所以他为了让其他同学也能理解他的痛苦，于是他准备向你询问T次，每一次输入一个正整数 $a$，请你找出最小的质数 $p$，使得 $a^p$ 和 $p^a$ 这两个正整数的（十进制）末位数字相同。如果不存在这样的质数，请输出 $-1$。

一组输入中包含多个询问。

输入格式

第一行一个正整数 $T$，表示询问数量。

接下来 $T$ 行每行一个正整数 $a$。

输出格式

对于每组数据输出一行答案。

2
9
12

19
-1

数据范围

对于所有数据，1≤T≤100,1≤a≤100000000。

Subtask 1 (30pts) : a ≤ 10.

Subtask2(70pts):无特殊限制。