CF2200H Six Seven

For positive integers $ i $ and $ j $ , define $ f_i(j) $ as the maximum integer $ k $ such that $ i^k $ divides $ j $ . A number $ j $ is considered special if $ f_6(j) \gt f_7(j) $ . For example, $ 6 $ is special, but $ 67 $ and $ 7 $ are not. You are given an array $ a $ of $ n $ positive integers. In one operation, you must increase every element in the array by $ 1 $ . Your task is to find the minimum number of operations needed to make all elements in $ a $ special at the same time, or determine that it is impossible.

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ), the number of test cases. For each test case, the first line contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ). The sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single integer: the minimum number of operations to make all elements special at the same time, or $ -1 $ if it is impossible.

In the first test case, all elements cannot be made special at the same time. In the second test case, performing $ 5 $ operations results in the array $ [30,72] $ , whose elements are all special. In the fourth test case, the array becomes $ [9557358] $ after $ 7 $ operations.