Problem B: Ladder

Trisanku wanted to ascend to Swarga (Heaven) by building a ladder all the way from earth to heaven. He undertook rigorous penance seeking boons from the trinity Brahma, Vishnu and Siva. Pleased by his austerities, the three Gods appeared before him first and gave him the following boon. They asked him to choose three prime numbers (b, v, s) one for each of them and then guaranteed that they would magically ensure that if there was any rung on the ladder at any height h above the ground, they would ensure there were rungs also at heights b + h, v + h and s + h. Trishanku built only the first rung at a height of 1 feet from the earth and then invoked the boon. Magically many more rungs appeared as promised. Trishanku began the assiduous climb to heaven going up one rung of the ladder at a time. He kept track of various statistics along the way, such as what height he was at and how many rungs he had climbed so far and the sequence of gaps between any two consecutive rungs he had climbed. He maintained all this data in a bulky journal which slowed his progress. Your job is to help Trisanku by writing a program that will eliminate the need to keep such bulky journals of data. Your program should read as input the three prime numbers and then answer the following three types of queries.

1. Given any height n ft above the earth, how many rungs are there in the ladder at or below height n from the earth.
2. Given the number n of rungs that Trisanku has climbed, what is biggest gap between any two consecutive rungs he has encountered so far.
3. Given a gap value n, after how many rungs from the bottom does this gap appear (if it appears at all) for the first time between two rungs on the ladder. If gap does not appear, print a 0.

You can assume that all values given/calculated for these queries will fit in a 32 bit integer.

Input

First input line is the number of test cases for the program. The next line is the b v s values (three primes separated by a single space) for this test case. Queries for this test case follow, one query per line. Each query will have 2 numbers separated by a single space. The first number is the query type (1, 2 or 3) and the second number is the value of $n$ for this query. A line with 0 terminates the queries for this test case.

Output

Output will be one number per line- the answer for each query in the same order as the queries. Ouptut lines should be consecutive with no blank lines between test cases.

Sample Input

2
11 13 17
1 20
3 5
0
11 23 37
2  4
0

Sample Output

4
4
11