Jair and Chadan are very close friends of Mr. Ed; this legendary couple even accompanied him to the World Finals many years ago! When they got bored of fixing windows, these buddies invited Mr. Ed to have dinner tonight and play their favourite hipster board game: “Not a board game”. “Not a board game” is a well-known game among hipsters (probably you never hear about it). In this game, n cards with the numbers from 1 to n are put on a table facing down; each number appears exactly in one card. The objective of the game is to form an integer in base n + 1 using all the cards... there is no winner, no score, no rules... you are free to enjoy the game just as it is. Anyway, Chadan is even more hipster than that, he invented an underground way of playing. Initially k cards are flipped up, then, two players alternate turns to play. On each turn, a player must choose a card and add it to the end of the formed integer. There is only one rule to choose a card: if there is at least one card facing up, the player must choose a face up card; in other case, the player may choose any card he wants. Notice that the player in turn can look the value of each card in the table, even if the card is facing down. After choosing a card and adding it to the formed integer, all the cards with a prime factor of the chosen card are flipped; cards facing up are flipped down and vice versa. Mr. Ed is watching Jair playing against Chadan. He knows that Jair started the game and aims to form the highest number, while Chadan plays in order to form the lowest number, so he is now wondering: assuming each one plays optimally, which will be the resulting number? By “optimally” we mean that, on each turn, they both choose a card that guarantees no other choice results in a higher (for Jair) or lower (for Chadan) integer at the end of the game. Input The first line contains an integer number T corresponding to the number of cases. The next T lines contains two space-separated integer numbers 1 ≤ n ≤ 10,000 and 1 ≤ k ≤ min(100, n) representing the amount of cards in the game and the number of cards initially flipped up, followed by k distinct integers representing the initial k cards that had been flipped up. Output For each test case output a line with the resulting integer in decimal base (see format below). Since this number can be huge, you must print it modulo 1,000,000,007 (109 + 7). Sample Input 3 20 312 7512467 Sample Output Case #1: 7 Case #2: 39 Case #3: 1894165