시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 84 | 63 | 43 | 78.182% |
We inductively label the nodes of a rooted binary tree with an infinite number of nodes as follows:
By having this tree in our hand, we define a rational sequence a1, a2, a3, … by a breadth first traversal of the tree in such a way that nodes in the same level are visited from left to right. Therefore, we have a1 = 1/1, a2 = 1/2, a3 = 2/1, a4 = 1/3, a5 = 3/2, …
You are to write a program that gets values p and q and computes an integer n for which an = p/q.
The first line of the input includes the number of test cases, 1 ≤ t ≤ 1000. Each test case consists of one line. This line contains p, followed by / and then q without any space between them.
For each test case, output in one line an integer n for which an = p/q. It is guaranteed that in all test cases n fits in a 32-bit integer.
4 1/1 1/3 5/2 2178309/1346269
1 4 11 1431655765
ICPC > Regionals > Asia West Continent > Iran > Iran Internet Programming Contest > IIPC 2015 E번