Welcome to the semifinal round of the Olympiad! In order to successfully pass this round, the organisers consider that the average student's grade should be no less than 3.5, and the grade for computer science should be A or B. The organisers also believe that not all students will be able to go to the finals, but they may be wrong, as this task is still not solved. Solve this problem by writing a program that will be able to identify students who have passed and have not passed to the final round.

Input

First line contains the number of students n (1 ≤ n ≤ 1000). Each of the next n lines contains: number xi (0.0 < xi ≤ 5.0) - average grade of the i-th student and one symbol yi (yi ϵ {A, B, C, D, E, F}) - computer science grade of this student. Students are numbered from 1 to n.

Output

For each student in a separate line print 1 if the student goes to the final, or 0 otherwise.