题目描述

给定一个正整数 X，请你在 X 后面添加若干位数字（至少添加一位数字；添加的数不能有前导 0），使得结果为质数，在这个前提下所得的结果应尽量小。

补充：前导 0 指 整型数字前面的 0 ,对数字的值来说没有意义，比如 00123。去掉前导 0 指的是去掉数字前面的 0 。

输入数据

第一行包含一个整数 T，表示共有 T 组测试数据。

每组数据占一行，包含一个整数 X。

输出数据

每组数据输出一行结果，一个整数，表示所得的满足条件的最小质数。

样例

1
1

11

数据范围与约定

1≤T≤100, 1≤X≤100。

提示

前导 0 指的是一个数字前有若干个 0，本题不允许后加带前导 0的数，如 05，0018这类数字是不被允许的