Batman has come to visit RUET. All on a sudden Ironman has landed in front of Low CG Chottor. "Oh, the black and white DC guy!", Ironman said.
"Big man in a suit of armor. Take that away and what are you?", Batman said back.
"A genius, billionaire, playboy, philanthropist.", replied Ironman. "What is your superpower?", Ironman asked.
"I am rich.", replied Batman.
"Then prove it.", said Ironman.
Then they approach each other to start a fight. Suddenly Joker arrived there and said, "Vai thamen."
Joker gave each of them a deck of cards. Ironman got N number of cards in his deck (numbered from 1 to N) and Batman got K number of cards in his deck (numbered from 1 to K). Then Joker gave a cruel smile and told them, "Asen kheli."
Both of them will shuffle their card decks randomly. Then they start to show their cards from the top. First, they show the top cards of each of their decks. If those cards don't match, they will show their 2nd top cards from their decks. If the 2nd top cards also don't match, then they will show their 3rd top cards and so on.
If any card matches, then Batman will win the match and the game ends. And if there is not a single card match at the end of either deck, Ironman will win. Two cards are said to match when they have the same numbers on them.
After hearing the rules Batman said, "Khela Hobe!!"
Your task is to determine how many scenarios Ironman can win in. As the number can be very big, you need to modulo it by M.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing three integers: N, K, M. (1 <= N, K <= 100000 and 1 <= M <= 1000000000)
Output
For each case, print the answer in a single line in the format "Case X: Y" without the quotes, where X is the case number and Y is the answer modulo M.
Sample
| Input | Output |
|---|---|
2 1 1 10 2 2 7 | Case 1: 0 Case 2: 2 |
In the first test case, the only scenario possible is -
Ironman's cards: 1,
Batman's cards: 1
So, Ironman can never win.
In the second test case, the total possible scenarios are as followed.
Scenario 01 -
Ironman's cards: 1 2,
Batman's cards: 1 2
Scenario 02 -
Ironman's cards: 1 2,
Batman's cards: 2 1
Scenario 03 -
Ironman's cards: 2 1,
Batman's cards: 1 2
Scenario 04 -
Ironman's cards: 2 1,
Batman's cards: 2 1
Ironman wins in scenario 02 and scenario 03.
