40
304 20 3
105 6 1
336 10 3
352 2 3
315 6 3
370 1 3
345 8 3
378 15 3
201 7 5
555 9 5
end of input