Taco Flower Configurations

You are given a rectangular grid of size N x M. Each cell of the grid can have one of the K different types of flowers. Although a particular cell at position (X, Y) is designated as special, it does not affect the configuration count.

Your task is to compute the number of possible configurations for planting flowers in the grid, which is given by:

$$\text{configurations} = K^{(N \times M)}$$

For each test case, you will be provided the integers N, M, X, Y and K. The output should be the computed number of configurations. Note that the (X, Y) value is provided for possible future extensions, but it does not impact the calculation for this problem.

inputFormat

The first line of input contains an integer T, denoting the number of test cases. Each of the following T lines contains 5 space-separated integers: N, M, X, Y, and K.

outputFormat

For each test case, output on a separate line the value of K^N*M, which represents the number of configurations.

## sample

2
3 3 2 2 3
2 2 1 2 4

19683
256

</p>