spoj
Състезание
Задача
D
Наименование
МНОГОЧОРАПЕНАТА

Условие

Мими Многочорапената... притежава много чорапи! Тя притежава общо N чифта чорапи, като на всеки P-ти ден се сдобива с нов чифт (това са дните с номера P, 2P, 3P ...). Тя е суеверна и спазва добра хигиена, затова никога не обува нови чорапи в деня, в който ги е получила. Освен това Мими не обича да носи едни и същи чорапи отново – в началото на деня тя слага чифт, който досега не е носила, а накрая този чифт отива в специален "Чорапен архив". Понеже Мими е много притеснена, а вие сте неин добър приятел, тя ви моли за една много специална услуга – направете програма, която изчислява колко време може да "оцелее" по този начин без да остане боса.

Вход: 
На първия ред на стандартния вход е зададен броят T на тестовете. Всеки тест се състои от 2 реда. На първия ред е зададено цялото число N – брой чифтове, които тя притежава в началото (1 ≤ N ≤ 100), а на втори ред е задено цялото число P (1 < P ≤ 100) – показващо на колко дена тя получава нови чорапи.

Изход: 
За всеки тест, програмата Ви трябва да изведе на отделен ред една стойност – броя на дните, през които Мими е имала чорапи. 

Примерен вход:
5
2 2
9 3
10 2
100 100
1 99	

Примерен изход:
3
13
19
101
1

Пояснение на примера: 
В първия тест Мими започва с 2 чифта, които носи през първите 2 дни. На втория ден тя е получила нов чифт, който може да обуе най-рано на третия ден, което и прави. Но тъй като на всеки два дни получава само по един нов чифт, тя няма нов чифт за четвъртия ден и тогава остава боса. Следователно е оцеляла с чорапи само 3 дни.

Във втори тест Мими започва с 9 чифта, които носи в продължение на първите 9 дни. През това време тя е получила нови чифтове по време на ден 3, 6 и 9, които ѝ помагат да стигне съответно до ден 10, 11 и 12. Докато носи последните си чорапи, по време на 12-тия ден тя получава нов чифт, който ѝ стига и за 13-тия ден. За съжаление, тя няма късмет и на 14-тия ден остава боса, понеже не е дочакала появата на новия чифт. 

В останалите тестове логиката е аналогична.

« Предходна страница Решение Въпрос