{"raw_statement":[{"iden":"statement","content":"You're playing a card game with K friends of yours, and since you're a champion in this game, they will play together and you will only play with the winner. \n\nAnd now when they are playing your job is just to deal N cards and distribute them among your friends, you can choose how to distribute them, but the distribution should satisfy these rules: \n\n1- Each player must have a continuous subsequence of the original set. \n\n2- Each card must be dealt to some player. \n\n3- Each player must have at least one card. \n\nNote that it is not important that players have the same number of cards. \n\nYou know that all of them are playing using the same strategy so the player with the maximum card group power will win. Each card has a power P the power of group of cards is calculated as (the number of cards in that group) * (the maximum value in the same group). \n\nSince the winner will play with you, and he will play using the same group of cards, you decided to minimize the power of his cards as much as you can. \n\nWrite a program to help you to do so. \n\nIn the first line one integer T the number of test cases. \n\nFor each test case there will be two integers N and K (1 ≤ N ≤ 1000000 , 1 ≤ K ≤ min(N, 20000)), then N integers representing the power of the cards in the original set and their order. (1 ≤ Pi ≤ 1000000).\n\nFor each test case print a single line containing one integer which is the minimum group power you can make the winner player have.\n\n"},{"iden":"input","content":"In the first line one integer T the number of test cases. For each test case there will be two integers N and K (1 ≤ N ≤ 1000000 , 1 ≤ K ≤ min(N, 20000)), then N integers representing the power of the cards in the original set and their order. (1 ≤ Pi ≤ 1000000)."},{"iden":"output","content":"For each test case print a single line containing one integer which is the minimum group power you can make the winner player have."},{"iden":"examples","content":"Input110 31 2 3 4 5 6 7 8 9 10Output25"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ p_m $ denote the $ m $-th prime number.  \nLet $ D(k) $ denote the number of positive divisors of $ k $.  \n\nLet $ S(N, M) = \\{ i \\in \\mathbb{Z}^+ \\mid D(i) = N \\text{ and all prime factors of } i \\leq p_M \\} $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 5 \\cdot 10^5 $  \n2. For each test case: $ 1 \\leq N \\leq 2 \\cdot 10^6 $, $ 1 \\leq M \\leq 10^9 $  \n\n**Objective**  \nFor each test case, compute $ |S(N, M)| \\mod (10^9 + 7) $.","simple_statement":"Given T test cases. For each test case, given N and M, count how many positive integers have exactly N divisors and all their prime factors are among the first M primes. Answer modulo 10^9+7.","has_page_source":false}