##### Eugene and big number

Eugene has to do his homework. But today, he is feeling very lazy and wants to you do his homework. His homework has the following given maths problem.

You are given three integers: **A**, **N**, **M**. You write the number **A** appended to itself **N** times in a row. Let’s call the resulting big number **X**. For example, if **A = 120, N = 3**, then **X** will be **120120120**. Find out the value of **X **modulo **M**.

### Input

The first line of the input contains an integer **T** denoting the number of test cases. The description of **T** test cases follow.

Each test case is described in one line containing three integers: **A**, **N** and **M** as described in the problem statement.

### Output

For each test case, output a single line containing an integer denoting the value of **X** modulo **M**.

### Constraints

**1**≤**T**≤**10**^{5}**0**≤**A**≤**10**^{9}**1**≤**N**≤**10**^{12}**2**≤**M**≤**10**^{9}

### Subtasks

**Subtask #1 (15 points):**

**0 ≤ A ≤ 100****1 ≤ N ≤ 10**^{5}

**Subtask #2 (25 points):**

**1 ≤ N ≤ 10**^{9}

**Subtask #3 (60 points):**

**Original constraints**

### Example

Input:2 12 2 17 523 3 11Output:5 6

### Explanation

**Example 1:** As **A = 12, N = 2, X = 1212**, **1212 modulo 17 = 5**

**Example 2.** As **A = 523, N = 3, X = 523523523**, **523523523 modulo 11 = 6**

Solution:Working on the Solution. Comment to discuss. Current Solution is having TLE.