Петя и Гена любят играть в настольный теннис. Игра идет по следующим правилам: партия состоит из нескольких сетов, каждый сет состоит из нескольких розыгрышей. Каждый из розыгрышей выигрывает один из игроков, ему присуждается одно очко. Как только один из игроков набирает t очков, ему присуждается победа в сете; после этого начинается следующий сет и счет выигранных розыгрышей обоих игроков обнуляется. Как только один из игроков выигрывает в сумме s сетов, ему присуждается победа в партии и игра заканчивается. Здесь s и t — некоторые целые положительные числа.
Чтобы разнообразить игру, Петя и Гена выбирают новые числа s и t перед каждой партией. Кроме этого, для истории ход каждой партии записывается: для каждого розыгрыша указывается, кто его выиграл. Розыгрыши записываются в хронологическом порядке. В записи партии сет завершается, как только один из игроков набрал t очков, и партия завершается, как только один из игроков выиграл s сетов.
Петя и Гена нашли запись старой партии. К сожалению, последовательность розыгрышей в записи не разделена на сеты, и числа s и t для данной партии тоже утеряны. Теперь игрокам интересно, чему могли быть равны s и t. Сможете ли вы определить все возможные варианты?
Выходные данные
В первой строке выведите одно число k — количество вариантов для чисел s и t.
В каждой из следующих k строк выведите по два числа si и ti — очередной вариант для чисел s и t. Варианты следует выводить в порядке возрастания si, а при равенстве si — в порядке возрастания ti.