J. How did we get here?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given Speed, Haste, Strength, Instant Health, Regeneration, Resistance, Fire Resistance, Jump Boost, Nausea, Weakness, Poison, Wither, Health Boost, Absorption, Saturation, Glowing, Bad Omen, Levitation, Dolphin's Grace, Conduit Power, Water Breathing, Slow Falling, Luck, Bad Luck.

Since the answer can be very small, print it modulo answer+1.

Input

A lot of pairs of positif integers

Output

A lot of single integers

Example
Input
6
0 3
0 4
0 5
4 9
73267 73267
23 1238916
Output
6
10
15
39
73267
767457046733