
126  The 10th Zhejiang Provincial Collegiate Programming Contest  C
Define S[n] as the number of subsets of {1, 2, ..., n} that contain no consecutive integers. For each S[n], if for all i (1 ≤ i < n) gcd(S[i], S[n]) is 1, we call that S[n] as a Prime S. Additionally, S[1] is also a Prime S. For the K^{th} minimum Prime S, we'd like to find the minimum S[n] which is multiple of X and not less than the K^{th} minimum Prime S. Please tell us the corresponding (S[n] ÷ X) mod M. InputThere are multiple test cases. The first line of input is an integer T indicating the number of test cases. For each test case, there are 3 integers K (1 ≤ K ≤ 10^{6}), X (3 ≤ X ≤ 100) and M (10 ≤ M ≤ 10^{6}), which are defined in above description. OutputFor each test case, please output the corresponding (S[n] ÷ X) mod M. Sample Input1 1 3 10 Sample Output1 