Description

Format

Input

Output

Samples

2
1 1
1 1
2 10 1000003

142

Limitation

对于100%的测试数据：

1<= k<=15

1 <= m <= n <= 1018