You are given two numbers X and Y.

You will have to find the value of (2^x)^y % 6.

INPUT

The first line will contain t number of test cases.

Next t lines will contain two numbers X and Y.

OUTPUT

For each testcase print single integer as answer.

CONSTRAINTS

1 <= t <= 10

1 <= X <= 10¹⁸

1 <= Y <= 10¹⁸

Be careful of the languages provided. only a few languages are provided. python is not provided to do this.

Partial marking is also there.