LNC Stones Game

LNC loves numbers that, in base \(k\), have the property that the product of their digits (when none is zero) divides the number itself. Such numbers are called LNC numbers. For example, when \(k = 10\), \(36\) is an LNC number because \(3 \times 6 \mid 36\). When \(k = 4\), \(12_4\) equals \(6_{10}\) and is an LNC number since \(1 \times 2 \mid 6\). However, when \(k = 2\), \(1101_2 = 13_{10}\) is not an LNC number because the product of its digits becomes 0, and 0 does not divide 13.

In this game, LJJ gives you \(x\) stones. LNC then chooses an integer base \(k\) (with \(k \ge 2\)). The players take turns removing some stones, but each move must remove a number of stones that is an LNC number in base \(k\) (when the move’s number is interpreted in decimal). LNC moves first, and whoever takes the last stone wins. Both players play optimally.

Your task is: given \(T\) games with a number \(x\) for each game, determine the minimum \(k\) (\(k \ge 2\)) that guarantees a win for LNC (the first player).

inputFormat

The first line contains an integer \(T\), the number of test cases. Each of the next \(T\) lines contains one integer \(x\) (\(1 \le x\le N\)), representing the number of stones in that game.

outputFormat

For each test case, output a single line containing the minimum integer \(k\) (with \(k \ge 2\)) for which LNC, playing first with optimal strategies, is guaranteed to win the game.

sample

1
1

2