In HackerLand, they have a very strange monetary system. Each gold coin has an integer number 'N' written on it. A coin N can be split into any number of coins. For example {\(11\)} can be split into \({5,6}\) or \({2,4,5}\) or any other possible way.
You are offered such a coin to take home. But your family does not like coins which have a prime number on it. Your task is to take home as few coins as possible without a prime number on it.
Input:
The first line of the input contains a single integer T denoting the number of test cases to follow. Each test case is a single line with a number N. It is the number written on your coin. Constraints:
\(1 \le T \le 100\)
\(1 \le N \le 100,000\)
Output:
For each test case output a single line, containing the minimum number of coins.
Test case 1: \({11}\) -> \({1,10}\). So, you can take home a possible minimum of 2 coins. NOTE: 1 is non-prime.
Test case 2: \({12345}\) can be taken home without splitting. Similar for the rest of the test cases.
