504055 - 幂的幂

【题目描述】幂的幂(power)

给4个数a,b,c,d,求a^(b^c )%d的值。

Input

第一行一个整数T(1≤T≤10000),表示测试数据组数。 随后T行,每行四个整数a,b,c,d(1≤a,b,c,d≤10^9)。

Output

输出T行答案。

Examples

Input

3
2 2 2 2
2 2 2 10
3 4 5 11

Output

0
6
4

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题