BANG! Loud sound of warning sirens had filled the living and service rooms of the space cruiser “Admiral Brisko” — flagship of 3rd earth fleet. It was on the way to Sirius, when light Zerg scout-ship appeared from nowhere.

— Capta-a-ain!
— Quiet! Damage report!
— Captain! Before the enemy ship was destroyed, it had damaged our left reactor, left engine and the onboard computer. We are doomed! They will intercept and destroy us!

It was absolutely useless to even try to get to Sirius without left engine. The same was about returning to the Earth: enemy ship certainly reported their coordinates to the rest of Zerg fleet, and light Zerg interceptors could be already on the way to their feeble cruiser with only one goal. And this goal was not to help them to repair the left engine…
There was only one solution — try to reach the nearest Mars space station. Uh! You don’t know what is a Mars space station?! It is a new defensive weapon of Martians — mobile, well defended and almost invulnerable space fort for defense of strategically important routes of Union of Five (union of the Earth, Mars, Venus, Andromeda and Sirius). There are many space stations located in special way along such important routes. Every space-week, in order to maintain secrecy the positions of space stations change according to weekly updates of the Secret Mars Key (SMK)!

— Call the programmer here! — bark out the captain.

Let’s guess what is your role here? Right! Here is your play! You task is to write program for calculation of the distance to the next space station — “Andromeda-Sirius-4”. It’s good that the secret algorithm of the station positioning is not a secret at all! Mmm… May be except Martians themselves… It’s quite simple: first base is located at the distance equal to SMK from the beginning of the path (Sirius in our case). The next station is located at the distance of F(SMK) from the first. Third station — at the distance of F(F(SMK)). And so on. Here F — is the Top Secret Mars Function (TSMF) It’s value is the sum of the cubes of digits its argument in decimal notation (for example F(12) = 1^3 + 2^3 = 9). So if the distance from the (I − 1)-th to I-th stations is X, then the distance between I-th and (I + 1)th stations is F(X). “What a nonsense?!” — you’ll say. And you will be absolutely right, but you should not be so strict — the authors of that idea were just small pretty downy rabbits — Martians.

Your cruiser is located between (N − 1)-th and N-th space stations at the distance of L from (N − 1)-th station. Taking N, K (Secret Mars Key) and L as input your program should output the distance M between your cruiser and N-th station. Oh, by the way! The value of SMK is always divisible by 3. It’s normal for Martians — all their numbers are divisible by 3.

Number T (2 ≤ T ≤ 33333) is placed in the first line of input — it is the number of tests for your program. It followed by the next T lines. Each of these T lines contains 3 integer numbers: N (2 ≤ N ≤ 33333), K (3 ≤ K ≤ 33333) and L (L ≥ 1).

T lines. I-th line contains the calculated value of M for I-th test case.