BFGCD - Cut The Rope

no tags 

Budi is a rope seller, He initially has two ropes to sell with length a and b where a and b is positive integer less than 10100. One day he meet with strange rich customer, the customer want to buy all rope with equal length only. Budi has an idea to sell all his rope to that customer: cut the rope until all his rope become equal length. Because Budi want maximum profit, he need to minimize the "cut" operation. But the customer doesn't like waiting, so Budi must calculate and do "cut" operation quickly. The customer can wait 60 seconds only, Budi can cut the rope in exactly 10 seconds, so Budi have 50 seconds to calculate number of "cut" operation needed. Help Budi to calculate number of "cut" operation and length of each rope after cutting process done. But unfortunately your modern calculator isn't working, so the only way to do is using brainf**k calculator, with 8 valid commands only. Will you help Budi?

Input

First line of input there is an integer T ≤ 1000 denoting number of test case.

Next T lines there're two positive integer a and b denoting length of rope that Budi has initially. Separated by a space (ASCII:32).

Each line is terminated with newline character (ASCII:10).

Output

For each case, output two number: first number is minimum number of cut operation, and second number is length of each rope after cutting process done.

Example

Input:
4
1 42
42 1
42 42
12345 67890

Output:
41 1
41 1
0 42
5347 15

Other Info

Input: generated 99.9% random with average digit is about 74.8 digits
Output: Average digit for "cut" operation is about 34.7 digits, and length of rope after cutting process done is about 49.0 digits.
This problem is using custom judge, so you can see the detail after you get AC/WA.
Judge output format is like this: ("Code Length (Valid Command only)")"Cell Used"("BF Command executed").
Click here to see my submission result for this problem.
Judge output for my BF code is: (11820)1157(6571171311) meaning that my Valid BF commands = 11820 commands and My code using 1157 BF cell and 6571171311 commands executed.
You can click (AC/WA) status for more detail.
My code running time is 6.95s and using 1.9M of memory.
Time limit is ~7× my BF program speed.


See also: Another problem added by Tjandra Satria Gunawan


hide comments
smso: 2019-04-20 07:17:35

You can only submit with 1 single rare language: brainf**k lang. No c++, java, ...
Don't waste your time here!

m888: 2016-12-25 19:25:48

what is a brainf**k languase ?

golden_flash1: 2015-09-10 20:22:47

Challenging problem !!

Last edit: 2015-09-10 20:23:31

Added by:Tjandra Satria Gunawan
Date:2013-07-15
Time limit:50s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:BF
Resource:Own Problem, Own Idea, Own Story, Own Custom Judge